Leetcode-264. Two Sum II - Input array is sorted

問題描述：

• Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
• The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you may not use the same element twice.
• *

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

• leetcode連結

解決思路

• 方法一：用hashmap

  用hashmap存儲已經周遊過的元素，key為值，value為該值在數組中的索引，從左向右周遊元素，周遊到目前元素 cur 時，檢查hashmap中是否已經有 target - cur 這個元素，若有，直接傳回。若沒有，則将該值加入到map中，注意：若是數組中有重複元素，那麼hashmap隻維護第一次出現該值的索引。

  時間複雜度：O(N) 空間複雜度：O(N) 适用情景：原數組排不排序都可以

• 方法二： 二分查找（Binary Search）

  該方法運用到了數組已經排好序這個性質，自然而然想到了二分查找。

  從左向右周遊該數組，每一次固定目前元素nums[i], 看 i+1~nums.length-1 範圍内有沒有出現 target- nums[i]這個值，而查找該值的方法便是二分查找。

• 方法三： 雙指針 (Two Pointer)

  用 l 和 r 兩個左右兩個指針，起初 l 在 0位置，r 在 nums.length -1位置，每一次都判斷nums[l] + nums[r] 是否等于target,若等于，直接傳回。否則，若該和大于 target,那麼右指針向左移動，若該和小于 target,那麼左指針向右移動。直至找到，或者左右指針重合

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

經驗教訓

• 由數組排序自然想到二分查找
• 注意雙指針做法

代碼實作：

• 方法一：用hashmap

public int[] twoSum(int[] nums, int target) {
        int[] res = new int[] {-,-};
        if (nums == null || nums.length ==  || nums.length == ) {
            return res;
        }
        HashMap<Integer, Integer> record = new HashMap<>();
        for (int i = ; i < nums.length; i++) {
            if (record.containsKey(target - nums[i])) {
                res[] = record.get(target - nums[i]);
                res[] = i;
                return res;
            }
            //有重複元素時，隻維護第一次出現時的索引
            if (record.containsKey(nums[i])) {
                continue;
            }
            record.put(nums[i], i);
        }
        return res;
     }
           

• 方法二： 二分查找（Binary Search）

public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length ==  || nums.length == ) {
            return new int[] {,};
        }
        for (int i = ; i < nums.length; i++) {
            int gap = target - nums[i];
            int l = i + ;
            int r = nums.length - ;
            while (l <= r) {
                int mid = l + ((r -l) >> );
                if (nums[mid] == gap) {
                    return new int[] {i + , mid + };
                }else if (nums[mid] > gap) {
                    r = mid - ;
                }else {
                    l = mid + ;
                }
            }
        }
        return new int[] {,};
     }
           

• 方法三： 雙指針 (Two Pointer)

public int[] twoSum(int[] nums, int target) {
        int[] res = new int[] {,};
        if (nums == null || nums.length ==  || nums.length == ) {
            return res;
        }
        int l = ;
        int r = nums.length - ;
        while (l < r) {
            long sum = nums[l] + nums [r];
            if (sum < target) {
                l++;
            }else if (sum > target) {
                r--;
            }else {
                return new int[] {l+, r+};
            }
        }
        return res;
     }