3. 有序数组中求和为给定值的两个数

2019-06-05 21:41:53

描述
这个题目说的是,给你一个整数数组,并且这个数组是按递增排序的,你要找到数组中的两个整数,它们的和等于给定的目标值,然后返回它们的下标。题目假设给你的数组总是有且只有一个解,而且同一个元素不能使用两次。另外,返回结果的下标要从 1 开始。
比如说给你的数组是:
1, 2, 3, 6, 8, 11
目标值是 10。那么,满足条件的两个整数是,2 和 8,它们的和是 10。所以你要返回它们的下标是 [2, 5]。
思路:
1.常规思路是两个指针,分别指向开始和末尾的元素,然后遍历一遍。如果大于target,那么右边指针左移;如果小于target,那么左边指针右移;
cpp实例.
class Solution {
public:
    vector twoSum(vector& numbers, int target) {
        int i=0, j=numbers.size()-1;
        vector result;
        while (i             int sum= numbers[i]+numbers[j];
            if (sum > target){
                j--;
            }
            if (sum < target){
                i++;
            }
            if (sum == target){
                result.push_back(i+1);
                result.push_back(j+1);
                break;
            }
        }
        return result;
       
    }
};
1234567891011121314151617181920212223
2.hashmap思路,python版本示例。从左到右遍历一遍,假设当前遍历的元素值为i,如果hash_map中没有,就把target-i加入到hash_map中去,值为当前遍历的索引。这样当发现当前的i存在于hash_map中,假设target=9,i=7,当前的7存在于hash_map中,就说明之前已经有9-7=2这个元素存在于hash_map中。非常巧妙。时间复杂度为O(n)。这种思路跟题目2中的思路一样,答案是相通的。
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
123
class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        hash_map = collections.defaultdict(lambda: 0)
        count = 0
        for i in numbers:
            count += 1
            if i in hash_map:
                return [hash_map[i], count]
            else:
                hash_map[target - i] = count
           
12345678910111213141516

         
         
---------------------
作者:TeacherLee_Netease
来源:CSDN
原文:https://blog.csdn.net/weixin_44986861/article/details/90613807
版权声明:本文为博主原创文章,转载请附上博文链接!

  • Copyright© 2015-2021 长亭外链网版权所有
  • QQ客服

    需要添加好友

    扫码访问本站