重庆建设工程信息网最新网站,云南网站建设崇左,给一个免费的网站,wordpress切换背景目录标题 2023-8-23 09:25:08 2023-8-23 09:25:08
自己写的不是常量级的额外空间#xff0c;但是写出来了#xff0c;记录一下。
下次写的时候#xff0c;请用双指针。
#xff08;其实我想了想一想#xff0c;双指针就没感觉出来#xff1a;因为我只想到双指针两个都… 目录标题 2023-8-23 09:25:08 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[]{i1, j1};}}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
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
