leetcode 167 Two Sum II - Input array is sorted

LeetCode


  1. Two Sum II - Input array is sorted:题目链接

方法1：暴力解法

暴力解法如下：

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
import java.util.Arrays;

public class Solution1 {
    // 时间复杂度O(N^2)  空间复杂度O(1)   暴力枚举法
    public static int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        // 双重循环遍历i和i之后的元素是否满足相加等于target
        for (int i = 0; i < numbers.length; ++i) {
            for (int j = i + 1; j < numbers.length; ++j) {
                // 如果满足条件  加入res中
                if (numbers[i] + numbers[j] == target) {
                    res[0] = i + 1;
                    res[1] = j + 1;
                    return res;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        System.out.println(Arrays.toString(twoSum(numbers, target)));
    }
}

方法2：二分查找法

从题目中提取有效条件，发现输入的数组都是有序的,又是查找两个元素，这不由让我想到了用二分查找法，二分法应用的前提就是连续的存储空间(数组不就是连续的嘛)，元素有序
基本思路： 指针i指向当前元素，在[i+1,nums.length-1]这个区间使用二分查找法寻找指针j满足numbers[i] + numbers[j] == target

二分查找法 递归与非递归形式详解：点击这里

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
import java.util.Arrays;
public class Solution2 {
    // 二分查找非递归
    public static int binarySearch(int[] numbers, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target > numbers[mid]) {
                left = mid + 1;
            } else if (target < numbers[mid]) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;       // 不存在 
    }

    // 二分查找递归
    public static int binarySearch2(int[] numbers, int left, int right, int target) {
        if (left > right) {
            return -1;    // 不存在
        }
        int mid = (right - left) / 2 + left;
        if (target > numbers[mid]) {
            return binarySearch2(numbers, mid + 1, right, target);
        } else if (target < numbers[mid]) {
            return binarySearch2(numbers, left, mid - 1, target);
        } else {
            return mid;
        }
    }

    // 如果用的是二分非递归 时间复杂度O(N*log2^N)   空间复杂度O(1)
    // 如果用的是二分递归     时间复杂度O(N*log2^N)   空间复杂度O(log2^N)
    public static int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        for (int i = 0; i < numbers.length - 1; ++i) {
            // j:利用二分查找看[i+1,nums.length-1] 是否存在j满足 numbers[i] + numbers[j] == target
            int j = binarySearch2(numbers, i + 1, numbers.length - 1, target - numbers[i]);
            if (j != -1) {    // 如果存在
                res[0] = i + 1;
                res[1] = j + 1;
                break;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        System.out.println(Arrays.toString(twoSum(numbers, target)));
    }
}


方法3：双指针之对撞指针

基本思想： 指针i从数组左侧开始往右侧移动，指针j从数组右侧往左侧移动

如果numbers[i] + numbers[j] > target,则说明numbers[j]大了，尝试j--，减小numbers[j]的值，注意数组是有序的
同理numbers[i] + numbers[j] < target,则说明numbers[i]小了，尝试i++，加大numbers[i]的值
如果numbers[i] + numbers[j] == target，则说明找到了
如果i和j相遇 还没有找到，说明不存在

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
import java.util.Arrays;

public class Solution3 {
    // 时间复杂度O(N)  空间复杂度O(1)  双指针之对撞指针
    public static int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        int[] res = new int[2];
        // 只要i和j没相遇 
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum > target) {
                j--;
            } else if (sum < target) {
                i++;
            } else {
                res[0] = i + 1;
                res[1] = j + 1;
                break;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        System.out.println(Arrays.toString(twoSum(numbers, target)));
    }
}

方法4：利用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 Solution4 {
    // 时间复杂度O(N) 利用hashMap
    public int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < numbers.length; ++i) {
            if (map.containsKey(target - numbers[i])) {
                res[0] = map.get(target - numbers[i]) + 1;
                res[1] = i + 1;
                break;
            } else {
                map.put(numbers[i], i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        System.out.println(Arrays.toString(new Solution4().twoSum(numbers, target)));
    }
}

pS: 相关源码链接

本文标题:leetcode 167 Two Sum II - Input array is sorted

文章作者:XerDemo

发布时间:2018-08-19, 16:16:00

最后更新:2018-09-05, 18:53:21

原始链接:https://xerdemo.github.io/2018/08/19/LeetCode解题/01-Array/leetcode-167-Two-Sum-II-Input-array-is-sorted/

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

文章目录
  1. 1. 方法1：暴力解法
  2. 2. 方法2：二分查找法
  3. 3. 方法3：双指针之对撞指针
  4. 4. 方法4：利用map
|