算法之two sum

leetcode : two sum

題目：求給定數據中的兩個值相加等於給定值，並返回這兩個數據在數據中的下標。

例如：數組[2, 7, 5 , 9 , 11]，給定值為9。數組中2+7=9，返回其下標[0,1]

分析：求x+y=9，外層循環取出每個數x， 再內層循環取出y，如果x+y=9，則找到x,y

方案一：暴力法，嵌套遍歷，時間複雜度O(N^2)

public static int[] twoSum(int[] nums, int target) {
 for (int i = 0; i < nums.length - 1; i++) {
 for (int j = i+1; j < nums.length; j++) { //注意內嵌從i+1開始到 length
 if (nums[i] + nums[j] == target) {
 return new int[]{i, j};
 }
 }
 }
 return null;
}

方案二：

• X+Y=9，轉換一下就是 X = 9 - Y，也就是在數組中找出X的位置。時間複雜度為O(n)
• 利用Map,Set來解決。時間複雜度為O(1)
• O(1) + O(N) = O(N)

public static int[] twoSum1(int[] nums, int target) {
 Map<integer> numsMap = new HashMap();
 for(int i = 0; i < nums.length; i++) {
 numsMap.put(nums[i], i);
 }
 for(int i = 0; i < nums.length; i++) {
 int k = target - nums[i];
 if(numsMap.containsKey(k) && numsMap.get(k) != i) {
 return new int[]{i, numsMap.get(k)};
 }
 }
 return null;
}
/<integer>

方法三：一遍哈希法

• 時間複雜度：O(N)
• 空間複雜度：O(N)

private int[] findIndex3(int[] nums, int target) {
 Map<integer> map = new HashMap();
 for(int i = 0; i < nums.length; i++) {
 int temp = target - nums[i];
 if(map.containsKey(temp) && map.get(temp) != i) {
 return new int[] {i, map.get(temp)};
 }
 map.put(nums[i], i);
 }
 throw new IllegalArgumentException("no two sum solution!");
}
/<integer>