第 1 天 求和问题

1. 两数之和

暴力枚举：略 O(N^2),O(1)
哈希表：O(N),O(N)

  1. public static int[] twoSum(int[] nums, int target) {
  2.     Map<Integer, Integer> hp = new HashMap<>();
  3.     for (int i = 0; i < nums.length; i++) {
  4.         if (hp.containsKey(target - nums[i])) {
  5.             return new int[]{hp.get(target - nums[i]), i};
  6.         }
  7.         hp.put(nums[i], i);
  8.     }
  9.     return new int[0];
  10. }

167. 两数之和 II - 输入有序数组

二分查找: O(nlogn) / O(1)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; ++i) {
            int low = i + 1, high = numbers.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/solution/liang-shu-zhi-he-ii-shu-ru-you-xu-shu-zu-by-leet-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

双指针：O(n) / O(1)

public static int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) {
                return new int[]{l + 1, r + 1};
            }
            if (sum < target) {
                l++;
            } else {
                r--;
            }
        }
        return new int[0];
    }