1、题目
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.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
2、代码实现
方法1:
通过2层循环解决，相当于把每个情况都便利出来，看是否有符合要求的没？代码如下：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> result; if (nums.empty() || (nums.size() == 0)) return result; for (int i = 0; i < nums.size() ; ++i) { for (int j = i + 1; j < nums.size(); ++j) { if (nums[i] + nums[j] == target) { result.push_back(i); result.push_back(j); return result; } } } return result; } };
你看上面不是说了嘛？you may not use the same element twice，特么我还i < nums.size(),如果i = nums.size() - 1, j = nums.size() -1这个时候恰好等于target的话，i == j,是自己没有注意，以后不要忘记，虽然通过程序了，但是呢？时间复杂度O(n*n),如果给我们的数组都是正数的没有顺序的，所以我么可以限制一些元素循环，比如if(ums[i] > target) continue,修改代码如下：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> result; if (nums.empty() || (nums.size() == 0)) return result; for (int i = 0; i < nums.size() － 1; ++i) { for (int j = i + 1; j < nums.size(); ++j) { if (nums[i] > target) continue; if (nums[i] + nums[j] == target) { result.push_back(i); result.push_back(j); return result; } } } return result; } };
方法2:
既然是从一个数组里面找到2个正确数据和为目标数据，我们用逆向思维，用目标数减去一个正确数据，那么差就是另外一个正确数据，如果减去的不是正确的数据，那结果肯定也不是正确的数据，我们可以把所有的数据装在hashmap里面，key为数据，value为下标，遍历每个数据，如果目标数据减去每个遍历的数据的差是hashmap里面的key,就可以了，我们可以得到value,也就是index.这样时间复杂度降低了，变成了O(n)
代码如下：
//import java.util.HashMap; public class Solution { public int[] twoSum(int[] nums, int target) { if (null == nums) return null; int[] result = new int[2]; HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; ++i) { Integer value = map.get(nums[i]); if (null == value) map.put(nums[i], i); Integer index = map.get(target - nums[i]); if (null != index && index < i) { result[0] = index; result[1] = i; } } return result; } }
这里为什么不把 下标设置成key，nums[i]设置成value呢？如果这样设置的话，我们每次put(i, nums[i]),我们target - nums[i]得到另外一个正确的值，但是我们程序需要的下表，我需要通过正确的nums[i],的到i,也就 是说通过value的到key,得不到吧，所以请注意，反过来就可以了。
特么我这么写还通过不了,下面就不写判断条件了，
import java.util.HashMap; public class Solution { public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; ++i) { Integer values = Integer.valueOf(nums[i]); if (!map.containkey(values)) map.put(i, nums[i]); Integer index = map.get(target - nums[i]); if (null != index && index < i) { result[0] = index; result[1] = i; } } return result; } }
提示出现：
Line 9: error: cannot find symbol: method containkey(Integer)
明天eclipse跑下，日了狗
C＋＋实现代码如下：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> result; if (nums.size() == 0 || nums.empty()) return result; map<int, int> map; for (int i = 0; i < nums.size(); ++i) { if (!map.count(nums[i])) { //特么我这里忘记写！，日了狗 map.insert(pair<int, int>(nums[i], i)); } if (map.count(target - nums[i])) { //这里自己傻逼了，写成map[target - nums[i]]了 int index = map[target - nums[i]]; if (index < i) { result.push_back(index); result.push_back(i); return result; } } } return result; } };
3、总结
1、写代码的时候要注意，如果有2个下标的话，第二个大需要j = i + 1,这样就永远大了，然后就是i 和 j不相等的话，注意i < nuns[i].size() - 1,不是i < nuns[i].size()，不这样的话i和j有可能就相等了。
2、我们为了降低时间复杂度，我们可以逆向思路，既然2个数加起来为目标数，那么目标数减去一个正确的数据，另外肯定是一个正确的数据，就可以通过map数据结构得到下标，
3、我们写代码的时候，一定要注意if(!map.count(nums[i])),不要写成了if(map.count(nuts[i])),不要忘记了!.
4、熟悉了C++的map用法和count函数是否包含key的作用。
