两数之和 II - 输入有序数组【LC167】
给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/array-and-string/cnkjg/
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
三个时间段的三种答案 神奇
- 我的题解
- 暴力
- 2021/11/15
class Solution { public int[] twoSum(int[] numbers, int target) { int[] index = {0,0}; for(int i =0;i<numbers.length;i++){ for(int j=i+1;j<numbers.length;j++){ if(numbers[i]+numbers[j] == target){ index[0] = i+1; index[1] = j+1; } } } return index; } }
双指针
2022/10/18
由于数组从小到大排列, 设置双指针分别指向数组的首部（left）和尾部(right)
- 若首部尾部相加等于目标值，返回结果集
- 若首部尾部相加小于目标值，右移left，使和变大
- 若首部尾部相加大于目标值，左移right，使和减小
- 代码
class Solution { public int[] twoSum(int[] numbers, int target) { int[] res = new int[2]; int len = numbers.length; int left = 0; int right = len-1; while(left < right){ if (numbers[left] + numbers[right] == target){ res[0] = left; res[1] = right; return res; }else if(numbers[left] + numbers[right] > target){ right--; }else { left++; } } return res; } }
- 复杂度
- 时间复杂度：O(n)，其中 n是数组的长度。两个指针移动的总次数最多为 n次。
- 空间复杂度：O(1)
二分查找
2023/7/8
依次遍历数组中的元素，然后使用二分法查找数组中是否存在元素的数值为targe-numbers[i]
- 若存在，则返回结果
- 若不存在，则继续遍历
class Solution { public int[] twoSum(int[] numbers, int target) { int n = numbers.length; for (int i = 0; i < n; i++){ int index = search(numbers, target - numbers[i], i + 1, n - 1); if (index != -1){ return new int[]{i + 1, index + 1}; } } return null; } public int search(int[] nums, int target, int l, int r){ while (l <= r){ int mid = (l + r) >> 1; if (nums[mid] == target){ return mid; }else if (nums[mid] > target){ r = mid - 1; }else{ l = mid + 1; } } return -1; } }
二分查找+双指针
class Solution { public int[] twoSum(int[] numbers, int target) { int i = 0, j = numbers.length - 1; while (i < j) { int m = (i + j) >>> 1; if (numbers[i] + numbers[m] > target) { j = m - 1; } else if (numbers[m] + numbers[j] < target) { i = m + 1; } else if (numbers[i] + numbers[j] > target) { j--; } else if (numbers[i] + numbers[j] < target) { i++; } else { return new int[]{i + 1, j + 1}; } } return new int[]{0, 0}; } } 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/502315
