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.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
Solution one:
对数组中的每一个数,遍历一次数组中的所有数,找到满足条件的两个数。
算法分析:时间复杂度O(n^2),空间复杂度O(1)。
class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { break; } } } return new int[] { i, j }; } }
Solution two:
在solution one的基础上改进时间复杂度。首先对数组进行排序(从小到大),然后定义两个指针,一个指针i从左到右,另一个指针j从右到左,比较nums[i]+nums[j]和target的大小:若nums[i]+nums[j]>target,则指针i右移;若nums[i]+nums[j] < target,则指针j左移;否则,返回结果。
算法分析:时间复杂度O(nlogn),空间复杂度O(n)。
class Solution { public int[] twoSum(int[] nums, int target) { Node[] tmp = new Node[nums.length]; int[] result = new int[]{0, 0}; for(int i = 0;i < nums.length; i++){ tmp[i] = new Node(i,nums[i]); } Arrays.sort(tmp); int i=0,j=nums.length-1; while(itarget){ j--; }else if(tmp[i].getValue()+tmp[j].getValue() { private int index; private int value; public Node(int index, int value){ this.index = index; this.value = value; } public int getIndex(){ return index; } public int getValue(){ return value; } @Override public int compareTo(Node node) { if(this.getValue()>node.getValue()){ return 1; }else if(this.getValue() Solution three: 转换一下思路,a+b=target ==>b=target-a。第一遍遍历数组,将(nums[index], index)依次存入HashMap;然后,第二次遍历数组,对于每一个nums[i],查找target-nums[i]是否在map中,若存在则返回结果。 算法分析:时间复杂度O(n)(java中HashMap的containsKey和get方法的实现都是常数时间的),空间复杂度O(n)。
Two-pass HashMap:
class Solution { public int[] twoSum(int[] nums, int target) { Mapmap = new HashMap<>(); for(int i = 0; i < nums.length; i++){ map.put(nums[i], i); } int i; for(i = 0; i< nums.length; i++){ int complement = target - nums[i]; if(map.containsKey(complement) && map.get(complement) != i){ break; } } return new int[] {i, map.get(target - nusm[i])}; } } One-pass HashMap:
class Solution { public int[] twoSum(int[] nums, int target) { Mapmap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } } BUG:当数组中有重复元素的时候可能会有一点小问题。