从零开始算法之路 ---- 167. 两数之和 II - 输入有序数组

朴灿烈づ我的快乐病毒、 2021-10-16 02:09 185阅读 0赞

**前言**:小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）  
**题源:** 力扣(LeetCode）[https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/][https_leetcode-cn.com_problems_two-sum-ii-input-array-is-sorted]  
**题目描述:**  
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

**说明:**

返回的下标值（index1 和 index2）不是从零开始的。  
 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。  
**思路：** 用目标 target 依次减去 numbers 数组中的值，再去 numbers 数组中寻找差，直到找到返回索引。利用迭代版二分查找。  
**C++版代码：**

class Solution { 
    public:
        	/** 思路: 用目标 target 依次减去 numbers 数组中的值，再去 numbers 数组中寻找差，直到找到返回索引。假装都能找到 */
        vector<int> twoSum(vector<int>& numbers, int target) { 
        	// 定义一个整型的 vector 存储结果索引
    		vector<int> result; 
    		int subtract;                                // 存储目标 target 减去 numbers 数组中的值的差
    		int index1, index2;                          // 存放要找两值的索引 
    		int temp;                                    // 存放二分查找返回结果 
    		int arraySize = numbers.size();              // 程序中频繁调用该函数，定义一个 size 变量存储，减少该函数调用次数，提供效率 
    		for(int i = 0; i < arraySize; i++){ 
    			subtract = target - numbers[i];
    			index1 = i+1;                            // 返回的下标值（index1 和 index2）不是从零开始的。
    			temp =  binarySearch( numbers, subtract, i+1, arraySize-1);
    			if(temp != -1) { 
    				index2 = temp + 1;                   // 返回的下标值（index1 和 index2）不是从零开始的。
    				break;                               // 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
    			}
    		}     
    		result.push_back(index1);
    		result.push_back(index2);    
    		return result;
        }
        // 迭代实现二分查找
    	int binarySearch(vector<int>& numbers, int target, int left, int right){ 
    		int medium;
    		while(left <= right){ 
    			medium = (left + right)/2;
    			if(target > numbers[medium])
    				left = medium + 1;
    			else if(target < numbers[medium])
    				right = medium - 1;
    			else 
    				return medium;    // 查找成功 
    		}
    		// numbers 没有想找的数值返回 - 1
    		return -1; 		
    	}    
    };

###### Java版代码： 思路一样，入参和出参不相同罢了。 ######

class Solution { 
        public int[] twoSum(int[] numbers, int target) { 
            int [] result = new int [2];                 // 存放结果索引
    		int subtract;                                // 存储目标 target 减去 numbers 数组中的值的差
    		int index1 = 0, index2 = 0;                  // 存放要找两值的索引,初始化为 0
    		int temp;                                    // 存放二分查找返回结果 
    		int arraySize = numbers.length;              // 程序中频繁调用该函数，定义一个 size 变量存储，减少该函数调用次数，提供效率 
    		for(int i = 0; i < arraySize; i++) { 
    			subtract = target - numbers[i];
    			index1 = i+1;                            // 返回的下标值（index1 和 index2）不是从零开始的。
    			temp =  binarySearch( numbers, subtract, i+1, arraySize-1);
    			if(temp != -1) { 
    				index2 = temp + 1;                   // 返回的下标值（index1 和 index2）不是从零开始的。
    				break;                               // 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
    			}
    		}
    		result[0] = index1;
    		result[1] = index2;
    	    return result;    
    	    }
        
    	// 迭代实现二分查找
    	public int binarySearch(int numbers[], int target, int left, int right){ 
    		int medium;
    		while(left <= right) { 
    			medium = (left + right)/2;
    			if(target > numbers[medium])
    				left = medium + 1;
    			else if(target < numbers[medium])
    				right = medium - 1;
    			else 
    				return medium;    // 查找成功 
    		}
    		// numbers 没有想找的数值返回 - 1
    		return -1;
    	}
    }

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