【JAVA】两数之和 II - 输入有序数组——力扣每日一题（七）（2020.07.20）_java一个有序数组,如果用最小时间复杂度,判断是否有两数之和s等于给定的数m

如果你从本文中学习到丝毫知识，那么请您点点关注、点赞、评论和收藏
大家好，我是爱做梦的鱼，我是东北大学大数据实验班大三的小菜鸡，非常渴望优秀，羡慕优秀的人，个人博客为：爱做梦的鱼https://zihao.blog.csdn.net/，微信公众号、微信视频号为【程序猿干货铺】，qq交流群为：1107710098，

如果你同样热爱算法，那么请关注我，我将每日更新力扣的每日一题的题解+代码，每周更新力扣周赛题解+代码
《本题JAVA代码版》
专栏《力扣每日一题》
专栏《力扣周赛》
专栏《力扣大厂模拟面试算法题》

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

本体链接（点击直接跳转）https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
1
2
3

前言

这道题可以使用 1. 两数之和 的解法，

1. 暴力求解,使用 O(n^2) 的时间复杂度和 O(1)的空间复杂度
2. 借助哈希表 使用 O(n)的时间复杂度和 O(n)的空间复杂度求解。

但是这两种解法都是针对无序数组的，没有利用到输入数组有序的性质。利用输入数组有序的性质，可以得到时间复杂度和空间复杂度更优的解法。

1. 二分查找，使用 O(nlogn) 的时间复杂度和 O(1)的空间复杂度
2. 双指针,使用 O(n) 的时间复杂度和 O(1)的空间复杂度

1.两数之和的官方题解，讲解了暴力求解和借助哈希表
作者：LeetCode
链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

167. 两数之和 II - 输入有序数组的官方题解，讲解了二分查找和双指针
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/solution/liang-shu-zhi-he-ii-shu-ru-you-xu-shu-zu-by-leet-2/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法一：暴力求解

思路
暴力法很简单，遍历每个元素 x，并查找是否存在一个与x相加为target 的目标元素。
代码

class Solution {
  public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++)
            for (int j = i + 1; j < nums.length; j++)//j从i+1开始，因为题目中说i和j不相等
                if (nums[j] + nums[i] == target)
                    return new int[]{i + 1, j + 1};//返回的下标值（index1 和 index2）不是从0开始的。从1开始的
        throw new IllegalArgumentException("No two sum solution");
    }
}
1
2
3
4
5
6
7
8
9

复杂度分析：

时间复杂度：O(n^2)
对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费O(n) 的时间。因此时间复杂度为 O(n^2)
空间复杂度：O(1)

方法二：借助哈希表

代码一：两遍哈希表

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (map.containsKey(diff) && i != map.get(diff)) {
                //i != map.get(diff):题目要求两个index1不能等于index2，不可以重复使用相同的元素
                return new int[]{i + 1, map.get(diff) + 1};
            }
        }
       throw new IllegalArgumentException("There is no solution to the sum of two numbers");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度分析：
时间复杂度：O(n)，
我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1)，所以时间复杂度为 O(n)。
空间复杂度：O(n)，
所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。

代码二：一遍哈希表

class Solution {
   public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (map.containsKey(diff)) {
                return new int[]{map.get(diff) + 1, i + 1};//建议考虑这个顺序
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("There is no solution to the sum of two numbers");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

复杂度分析：

时间复杂度：O(n)，
我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1)的时间。
空间复杂度：O(n)，
所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。

方法三：二分查找

代码

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])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        throw new IllegalArgumentException("There is no solution to the sum of two numbers");
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组的长度。需要遍历数组一次确定第一个数，时间复杂度是 O(n)，寻找第二个数使用二分查找，时间复杂度是 O(logn)，因此总时间复杂度是O(nlogn)。

空间复杂度：O(1)。

方法四：双指针

class Solution {
     public int[] twoSum(int[] numbers, int target) {
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            if (numbers[low] + numbers[high] == target)
                return new int[]{low + 1, high + 1};
            else if (numbers[low] + numbers[high] < target)
                low++;
            else
                high--;
        }
        throw new IllegalArgumentException("There is no solution to the sum of two numbers");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。两个指针移动的总次数最多为 n 次。
空间复杂度：O(1)