Problem describe:https://leetcode.com/problems/two-sum/
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]
AC code :
1.Bruth Algorithm
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int>& nums, int target) { 4 vector<int> res; 5 for(int i = 0;i < nums.size();i++) 6 for(int j = i + 1;j < nums.size();j++) 7 if(nums[i]+nums[j]==target) 8 { 9 res.push_back(i); 10 res.push_back(j); 11 } 12 return res; 13 14 } 15 };
2.Hashmap
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int>& nums, int target) { 4 vector<int> res; 5 unordered_map<int,int> map; 6 for(int i = 0; i < nums.size();i++) 7 { 8 map[nums[i]] = i; 9 } 10 for(int i = 0;i < nums.size();i++) 11 { 12 int left = target - nums[i]; 13 if(map.count(left) && i < map[left]) 14 { 15 res.push_back(i); 16 res.push_back(map[left]); 17 } 18 } 19 return res; 20 } 21 };
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
