leetcode 1. Two Sum

LeetCode


  1. Two Sum:题目链接

方法1：双指针

基本思路： 先对数组进行排序，然后一个指针left指向数组第一个元素，一个指针right指向数组最后一个元素,将两者相加，只有可能有三种情况

  1. nums[left] + nums[right] == target 找到了
  2. nums[left] + nums[right] < target 因为数组是有序状态 将left++ 及增大两者的和
  3. nums[left] + nums[right] > target 因为数组是有序状态 将right– 及减小两者的和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import java.util.Arrays;
public class Solution1 {
    // 时间复杂度O（Nlog2^N）
    public int[] twoSum(int[] nums, int target) {
        int[] tempArr = Arrays.copyOf(nums, nums.length);
        Arrays.sort(nums);
        int[] res = new int[2];
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                break;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        // 这里nums[left] + nums[right] 已经等于 target 但是不能直接返回 left，right 因为我们将数组排过序
        // 查找left
        for (int i = 0; i < tempArr.length; ++i) {
            if (tempArr[i] == nums[left]) {
                res[0] = i;
                break;
            }
        }
        // 查找right
        for (int i = tempArr.length-1; i>=0; --i) {
            if (tempArr[i] == nums[right]) {
                res[1] = i;
                break;
            }
        }
        // 如果left > right 交换
        if (res[0] > res[1]){
            int t = res[0];
            res[0] = res[1];
            res[1] = t;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {-1, -2, -3, -4, -5};
        int target = -8;
        System.out.println(Arrays.toString(new Solution1().twoSum(nums, target)));
    }
}

方法2：二分搜索

基本思路： 先将数组排序，遍历数组，当前指向元素left，如果用二分搜索法在[left, right]中发现target-nums[left]存在说明找到了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

import java.util.Arrays;
public class Solution2 {
    // 二分搜索非递归
    public int BinarySearch1(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;      // 没找到：-1
    }

    // 二分搜索递归
    public int BinarySearch2(int[] nums, int left, int right, int target) {
        if (left > right) {
            return -1;  // 没找到
        }

        int mid = left + (right - left) / 2;
        if (nums[mid] < target){
            return BinarySearch2(nums, mid + 1, right, target);
        }else if (nums[mid] > target){
            return BinarySearch2(nums, left, mid - 1, target);
        }else{
            return mid;
        }
    }

    // 时间复杂度O(Nlog2^N)
    public int[] twoSum(int[] nums, int target) {
        int[] tempArr = Arrays.copyOf(nums, nums.length);
        Arrays.sort(nums);
        int[] res = new int[2];

        int left = 0, right = 0;
        for (; left < nums.length; ++left) {
            right = BinarySearch1(nums, left + 1, nums.length - 1, target - nums[left]);
            if (right != -1) {
                break;
            }
        }
        
        for (int i = 0; i < tempArr.length; ++i) {
            if (tempArr[i] == nums[left]) {
                res[0] = i;
                break;
            }
        }

        for (int i = tempArr.length - 1; i >= 0; --i) {
            if (tempArr[i] == nums[right]) {
                res[1] = i;
                break;
            }
        }

        if (res[0] > res[1]) {
            int t = res[0];
            res[0] = res[1];
            res[1] = t;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {-1, -2, -3, -4, -5};
        int target = -8;
        System.out.println(Arrays.toString(new Solution2().twoSum(nums, target)));
    }
}

方法3： 利用map (推荐)

基本思路： 利用map，key存放元素的值 ，value存放元素的索引 ,遍历数组，当前指向元素索引为i，如果在数组中发现map的key中包含target - nums[i]，说明找到了.否则将该元素添加进map中，继续查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution3 {
    // 时间复杂度O(N)
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (map.containsKey(target - nums[i])) {
                res[1] = i;
                res[0] = map.get(target - nums[i]);
                break;
            }else {
                map.put(nums[i], i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 4};
        int target = 6;
        System.out.println(Arrays.toString(new Solution3().twoSum(nums, target)));
    }
}

pS: 在查找问题 而且数组有序 要想到 二分和双指针
源代码链接

本文标题:leetcode 1. Two Sum

文章作者:XerDemo

发布时间:2018-09-05, 19:42:05

最后更新:2018-09-05, 20:03:32

原始链接:https://xerdemo.github.io/2018/09/05/LeetCode解题/01-Array/leetcode-1-Two-Sum/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 方法1：双指针
  2. 2. 方法2：二分搜索
  3. 3. 方法3： 利用map (推荐)
|