【Leetcode】Two Sum

发布时间：2020-12-13 21:15:19 所属栏目：PHP教程来源：网络整理

导读：问题描写 Given an array of integers,return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution. Example: Given nums = [ 2 , 7 , 11 , 15 ],target = 9 ,Because

问题描写

Given an array of integers,return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2,7,11,15],target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].

给定1个数组和1个数，在数组中找到两个数，它们的和等于给定数，返回这两个数在数组中的索引。

问题分析

两重循环最简单，但肯定超时。数组排序是必须的，这样可以有1定的次序来求和。但如果顺序查找，就又是两重循环了。

所以，可以以这样的次序查找：从两头，到中间。保存两个指针，左侧1个，右侧1个，两个指针指向的数相加，会有以下结果和操作：

相加上和等于给定数，成功；
相加上和大于给定数，大了，右侧的指针左移，将两数之和减小；
相加上和小于给定数，小了，左侧的指针右移，将两数之和加大。

注：参数是援用，排序时要使用拷贝的数组

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums,int target) {
        // 复制数组，由于要排序 
        vector<int> cp(nums);
        // 先排序 
        sort(cp.begin(),cp.end());
        int right = cp.size()-1;
        int left = 0;
        while(right > left) {
            int sum = cp[right] + cp[left];
            if(sum == target) {
                break;
            } else if(sum < target) { // 数小了，left右移 
                left++; 
            } else if(sum > target) { // 数大了，right左移 
                right--;    
            }
        }
        vector<int> r;
        int a=-1,b=-1;
        // 取出索引 
        for(int i=0;i<nums.size();i++) {
            if(nums[i] == cp[left]&&a==-1) a = i;
            else if(nums[i] == cp[right]&&b==-1) b = i;
        }
        if(a>b) {
            int t = a;
            a=b,b=t;
        }
        r.push_back(a);
        r.push_back(b);
        return  r;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!