力扣 – 劍指 Offer 57. 和為s的兩個數字

• 2021 年 10 月 27 日
• 筆記
• 雙指針, 哈希表, 數組, 算法

題目

劍指 Offer 57. 和為s的兩個數字

思路1（哈希表）

• 這題首先想到的是使用兩個for遍歷，查找是哪兩個相加等於target，但是時間複雜度確實\(O(N^2)\)，時間複雜度太高，因此我們使用HashSet來解決
• 我們知道hash的查找速度是\(O(1)\)，因此遍歷到每個元素的時候判斷一下，target-nums[i]是否存在HashSet中，如果存在，則找到；如果不存在，那麼就將當前元素加入到HashSet中，繼續遍歷下一個元素，時間複雜度降低到了\(O()N\)，但是也使用了\(O(N)\)的空間複雜度，而且當前數組是排序數組的條件也沒有使用上

代碼

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashSet<Integer> set = new HashSet<>();

        // 只需遍歷一次數組
        for (int i = 0; i < nums.length; i++) {
            // 如果target-nums[i]在HashSet中，說明找到了
            if (set.contains(target - nums[i])) {
                return new int[]{nums[i], target-nums[i]};
            }
            // 否則要做的只是將當前元素添加到HashSet中
            set.add(nums[i]);
        }

        // 沒有找到的話返回一個空數組
        return new int[0];
    }
}

複雜度分析

• 時間複雜度：\(O(N)\)
• 空間複雜度：\(O(N)\)，哈希表所使用的空間

思路2（雙指針）

• 題目已經說了，數組是按照升序排序的數組，因此我們可以利用這個條件，使用雙指針解題
• 若數組為nums = [2,7,11,15], target = 9，則步驟如下：
  • 初始化左右指針left、right分別為：0、3(nums.length-1)
  • 將left、right位置的元素的值相加得17，大於target 9，說明我們兩個數之和的值需要向下調整，又因為數組是升序的數組，因此right指針向左移動一位，此時left為0，right為2
    • 再次相加，結果為13，還是大於target 9，因此right指針再次向左移動一位，此時left為0，right為1
    • 然後再相加，此時結果為9，等於target，所以我們找到了這兩個數返回即可

代碼

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;

        // 要保證left指針在right指針左邊
        while (left < right) {
            // 找到了
            if (nums[left] + nums[right] == target) {
                return new int[]{nums[left], nums[right]};
            } else if (nums[left] + nums[right] > target) {
                // 總和太大了，需要向小調整，故right向左移動一位
                right--;
            } else {
                // 總和太小了，需要向大調整，故left向右移動一位
                left++;
            }
        }
        // 沒找到
        return new int[0];
    }
}

複雜度分析

• 時間複雜度：\(O(N)\)
• 空間複雜度：\(O(1)\)，由於使用了雙指針，所以沒有使用額外的空間