【JAVA】两数之和 II - 输入有序数组——力扣每日一题（七）（2020.07.20）

女爷i 2023-02-28 11:12 3阅读 0赞

### 目录 ###

*  题目：167. 两数之和 II - 输入有序数组
 *  前言
 *  方法一：暴力求解
 *  方法二：借助哈希表
 *  方法三：二分查找
 *  方法四：双指针

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

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

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

[本体链接（点击直接跳转）https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/][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. 两数之和][1.] 的解法，

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzEyNDI3OQ_size_16_color_FFFFFF_t_70]

> 1.两数之和的官方题解，讲解了暴力求解和借助哈希表  
> 作者：LeetCode  
> 链接：[https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/][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/][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");
        }
    }

**复杂度分析：**

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

![在这里插入图片描述][20200724130841350.png]

# 方法二：借助哈希表 #

**代码一：两遍哈希表**

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");
        }
    }

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

![在这里插入图片描述][20200724132834338.png]

**代码二：一遍哈希表**

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");
        }
    }

**复杂度分析：**

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

![在这里插入图片描述][20200724141224929.png]

# 方法三：二分查找 #

**代码**

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");
        }

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

空间复杂度：O(1)。

![在这里插入图片描述][20200724190621119.png]

# 方法四：双指针 #

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");
        }
    }

**复杂度分析**

时间复杂度：O(n)，其中 n 是数组的长度。两个指针移动的总次数最多为 n 次。  
空间复杂度：O(1)  
![在这里插入图片描述][20200724191359592.png]

[Link 1]: https://blog.csdn.net/weixin_43124279
[https_zihao.blog.csdn.net]: https://zihao.blog.csdn.net/
[Link 2]: https://s1.ax1x.com/2020/06/11/tHUSvq.png
[1107710098]: https://s1.ax1x.com/2020/06/26/NroKrd.jpg
[Image 1]: 
[JAVA]: https://blog.csdn.net/weixin_43124279/article/details/107415356
[Link 3]: https://blog.csdn.net/weixin_43124279/category_10194088.html
[Link 4]: https://blog.csdn.net/weixin_43124279/category_10194115.html
[Link 5]: https://blog.csdn.net/weixin_43124279/category_10202733.html
[https_leetcode-cn.com_problems_two-sum-ii-input-array-is-sorted]: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
[1.]: https://leetcode-cn.com/problems/two-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzEyNDI3OQ_size_16_color_FFFFFF_t_70]: /images/20230209/7eb46b43fb8a43bc9b37d0a11577c68f.png
[https_leetcode-cn.com_problems_two-sum_solution_liang-shu-zhi-he-by-leetcode-2]: https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/
[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]: 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/
[20200724130841350.png]: https://img-blog.csdnimg.cn/20200724130841350.png
[20200724132834338.png]: https://img-blog.csdnimg.cn/20200724132834338.png
[20200724141224929.png]: https://img-blog.csdnimg.cn/20200724141224929.png
[20200724190621119.png]: https://img-blog.csdnimg.cn/20200724190621119.png
[20200724191359592.png]: https://img-blog.csdnimg.cn/20200724191359592.png