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.
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
給定一個int數(shù)組，一個指定的int型target，要求找出數(shù)組中相加等于target的兩個數(shù)的索引。假定每個輸入只有一個輸出。

答案

方法一：

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]) { 
         return new int[] { i, j }; 
      } 
    } 
  } 
  throw new IllegalArgumentException("No two sum solution");
}

時間復雜度：O(n^?2??)
空間復雜度：O(1)
實際運行時間：42ms

方法二：

public int[] twoSum(int[] nums, int target) { 
    Map<Integer, Integer> map = new HashMap<>(); 
    for (int i = 0; i < nums.length; i++) { 
        map.put(nums[i], i); 
    } 
    for (int i = 0; i < nums.length; i++) { 
        int complement = target - nums[i]; 
        if (map.containsKey(complement) && map.get(complement) != i) { 
            return new int[] { i, map.get(complement) }; 
        } 
    } 
    throw new IllegalArgumentException("No two sum solution");
}

時間復雜度：O(n??)
空間復雜度：O(n)
實際運行時間：8ms

方法三

public int[] twoSum(int[] nums, int target) { 
    Map<Integer, Integer> map = 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");
}

時間復雜度：O(n??)
空間復雜度：O(n)
實際運行時間：6ms

參考LeetCode-1