网站平台建设,镜像站wordpress,wordpress公告 通知栏插件,展示型网站设计公司给你一个下标从 1 开始的整数数组 numbers #xff0c;该数组已按 非递减顺序排列 #xff0c;请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] #xff0c;则 1 index1 index2 numbers…给你一个下标从 1 开始的整数数组 numbers 该数组已按 非递减顺序排列 请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 index1 index2 numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。 前言 这道题可以使用「1. 两数之和」的解法使用 O(n^2) 的时间复杂度和 O(1) 的空间复杂度暴力求解或者借助哈希表使用 O(n) 的时间复杂度和 O(n) 的空间复杂度求解。但是这两种解法都是针对无序数组的没有利用到输入数组有序的性质。利用输入数组有序的性质可以得到时间复杂度和空间复杂度更优的解法。
方法一二分查找 在数组中找到两个数使得它们的和等于目标值可以首先固定第一个数然后寻找第二个数第二个数等于目标值减去第一个数的差。利用数组的有序性质可以通过二分查找的方法寻找第二个数。为了避免重复寻找在寻找第二个数时只在第一个数的右侧寻找。
//二分法查找
class Solution {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]) { //target - numbers[i]为要寻找的第二个加数值return new int[] {i 1, mid 1};//生成新数组返回} else if (numbers[mid] target - numbers[i]) {high mid - 1;} else {low mid 1;}}}return new int[] {-1, -1};}
} 复杂度分析
时间复杂度O(nlogn)其中 n 是数组的长度。需要遍历数组一次确定第一个数时间复杂度是 O(n)寻找第二个数使用二分查找时间复杂度是 O(logn)因此总时间复杂度是 O(nlogn)。空间复杂度O(1)。
方法二双指针
复杂度分析 时间复杂度O(n)O(n)其中 nn 是数组的长度。两个指针移动的总次数最多为 nn 次。 空间复杂度O(1)O(1)。 //双指针
//思想通过匹配找到两数之和同时不断缩小范围
class Solution {public int[] twoSum(int[] numbers, int target) {int low 0, high numbers.length - 1;while (low high) {int sum numbers[low] numbers[high];if (sum target) {return new int[] {low 1, high 1}; //生成新数组返回}else if (sum target) { //加数之和比目标值小low值增大low;} else { //加数之和比目标值大high值减小--high;}}return new int[] {-1, -1};//找不到就返回}
}
