力扣 – 剑指 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)\)，由于使用了双指针，所以没有使用额外的空间