LeetCode：01:Two Sum

雨点打透心脏的1/2处 2022-06-08 11:27 119阅读 0赞

#### 题目描述： ####

> 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, and you may not use the same element twice.
> 
> Example:  
> Given nums = \[2, 7, 11, 15\], target = 9,
> 
> Because nums\[0\] + nums\[1\] = 2 + 7 = 9,  
> return \[0, 1\].

#### 题目分析： ####

给定一个数组和一个正整数，返回数组中和为正整数的下标，数组中的值只能使用一次。

#### 算法思路： ####

首先对数组进行排序，考虑到排序后下标可能与原数组下标不一致，所以创建一个结构体，保存数组的值和下标。  
用两个指针，分别从第一个和最后一个开始，如果和大于目标值，则后面的指针向前移动，如果和小于目标值，前面的指针向后移动，直到和等于目标值。

struct Node{
        int val;
        int idx;
        Node(int val,int idx):val(val),idx(idx){};
    };
    
    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> res;
            vector<struct Node> node;
            for(int i=0;i<nums.size();i++){
                node.push_back(Node(nums[i],i));
            }
            for(int i=0;i<node.size();i++){
                for(int j=0;j<i;j++){
                    if(node[i].val<node[j].val){
                        Node tem=node[i];
                        node[i]=node[j];
                        node[j]=tem;
                    }
                }
            }
            int i=0,j=node.size()-1;
            while(i!=j){
                if(node[i].val+node[j].val>target){
                    j--;
                }
                else if(node[i].val+node[j].val<target){
                    i++;
                }else {
                    res.push_back(node[i].idx);
                    res.push_back(node[j].idx);
                    return res;
                }
            }
            return res;
        }
    };