【LeetCode】167. 两数之和 II - 输入有序数组 - 双指针

2023-8-23 09:25:08

自己写的不是常量级的额外空间，但是写出来了，记录一下。

下次写的时候，请用双指针。

（其实我想了想一想，双指针就没感觉出来：因为我只想到双指针两个都向后，没想到一个也能够在前一个向后。Orz。多做点题目就好了。）

class Solution {public int[] twoSum(int[] numbers, int target) {int[] result = new int[2];// 从第一个i下标开始找for (int i = 0; i < numbers.length; i++) {// 找到i后面的下标for (int k = i + 1; k < numbers.length; k++) {// 由于 该数组已按 非递减顺序排列// 剪枝：相加之和大于目标数的话,后面的就可以不用判断了if (numbers[i] + numbers[k] > target) {break;}// 相加之和等于目标数 且 仅存在一个有效答案if (numbers[i] + numbers[k] == target) {// result[0] = i + 1;result[1] = k + 1;return result;}}}return result;}
}

O(n) 解法

public int[] twoSum(int[] numbers, int target) {int i = 0;int j = numbers.length - 1;while (i < j) {int sum = numbers[i] + numbers[j];if (sum < target) {i++;} else if (sum > target) {j--;} else {return new int[]{i+1, j+1};}}return new int[]{-1, -1};
}作者：nettee
链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/solutions/87919/yi-zhang-tu-gao-su-ni-on-de-shuang-zhi-zhen-jie-fa/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。