剑指 Offer 57. 和为s的两个数字

前提是题目给的是升序数组

双指针

时间复杂度O(n),空间复杂度O(1)

left和right指针判断当前和与目标的大小关系，大于，right左移，小于，left右移。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ans = new int[2];
        int left =0,right=nums.length-1;
        while(left<=right)
        {
            int tmp = nums[left]+nums[right];
            if( tmp == target)
            {
                break;
            }
            else if(tmp > target)
            {
                right--;
            }
            else
            {
                left++;
            }
        }
        ans[0]=nums[left];
        ans[1]=nums[right];
        return ans;
    }
}

哈希

这种方法在数组是无序的时候也有用，因为hash里面查找target-e只需要一次查找即可。

时间复杂度O(n),空间复杂度O(n)

这个遍历了两次数组

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashSet<Integer> set = new HashSet<>();
        int[] ans = new int[2];
        for(int e : nums)
        {
            set.add(e);
        }
        for(int e : nums)
        {
            if(set.contains(e) && set.contains(target-e))
            {
                ans[0] = e;
                ans[1] = target-e;
                break;
            }
        }
        return ans;
    }
}

下面遍历一次数组，set添加过程和寻找过程结合在一起

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];
    }
}