中文字幕一区二区无码成人,91美女网站,色婷婷AV无码久久精品,1级黄色毛片,天天草天天日天天干天天舔,久草福利在线视频,性爱视频在线无码播放,操出水视频在线观看网站国产

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?兩數(shù)之和 II - 輸入有序數(shù)組??，我們先來看題面：

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.

題意

給定一個(gè)已按照升序排列的有序數(shù)組，找到兩個(gè)數(shù)使得它們相加之和等于目標(biāo)數(shù)。

函數(shù)應(yīng)該返回這兩個(gè)下標(biāo)值 index1 和 index2，其中 index1 必須小于 index2。

說明:

返回的下標(biāo)值（index1 和 index2）不是從零開始的。

你可以假設(shè)每個(gè)輸入只對應(yīng)唯一的答案，而且你不可以重復(fù)使用相同的元素。

樣例

輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標(biāo)數(shù) 9 。因此 index1 = 1, index2 = 2 。

解題

https://blog.csdn.net/weixin_41943637/article/details/103343131

思路1:雙層循環(huán)

class?Solution?{
????public?int[] twoSum(int[] numbers, int?target) {
???????for?(int?i = 0; i < numbers.length; i++) {
????????????int?Num = target - numbers[i];
????????????for?(int?j = i + 1; j < numbers.length; j++) {
????????????????if?(Num == numbers[j]){
????????????????????int?nums[] = {i+1,j+1};
????????????????????return?nums;
????????????????}
????????????}
????????}
????????return?null;
????}
}

思路2:雙指針

前后雙指針分別指向數(shù)組的首尾，如果首尾元素相加大于目標(biāo)，則尾指針向前一位；反之，如果首尾元素相加小于目標(biāo)，則首指針向后一位。最差情況下，整個(gè)數(shù)組也只會遍歷一遍，所以時(shí)間復(fù)雜度為O(N)。

class?Solution?{ 
???public?int[] twoSum(int[] numbers, int?target) { 
??????int?left=0; 
??????int?right=numbers.length-1; 
??????while(left?????????int?sum=numbers[left]+numbers[right];
?????????if(sum==target)return?new?int[]{left+1,right+1}; 
?????????else?if(sum?????????else?if(sum>target)right--; 
??????} 
????return?null; 
????}
}

思路3:二分查找

class?Solution?{
????public?int[] twoSum(int[] numbers, int?target) {
????????for(int?i = 0; i < numbers.length; i++) {
????????????int?index = binarySearchIndex(numbers, i + 1, target - numbers[i]);
????????????if(index != -1) {
???????????????return?new?int[]{i + 1, index + 1}; 
????????????}
????????}
????????return?new?int[]{};
????}
????public?int?binarySearchIndex(int[] numbers, int?startIndex, int?target) {
????????int?low = startIndex;
????????int?high = numbers.length - 1;
????????while(low <= high) {
????????????int?mid = (low + high) >>> 1; 
????????????if(target > numbers[mid]) {
????????????????low = mid + 1;
????????????} else?if(target < numbers[mid]) {
????????????????high = mid - 1;
????????????} else?{
????????????????return?mid;
????????????}
????????}
????????return?-1; 
????}
}