LeetCode 1.Two Sum题目解析-wowAC

Description

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].

题目复述

    给你一个整型数组,返回数组中两个数的下标使得这两个数的和为一个特定的数,假定每组样例有且只有一组答案,并且你不能两次都选择数组中同一个数。

题目解析

1.暴力法

    暴力方法的思路是,首先确定一个数a, 然后再遍历一遍数组,找到一个数b使得a + b = target,整体来说还是很简单的。改方法的时间复杂度为O(n^2)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i + 1; j < nums.size(); ++j) {  //注意j的循环范围
                if (nums[i] + nums[j] == target) {
                    ret.push_back(i);
                    ret.push_back(j);
                    break;
                }
            }
            
            if (!ret.empty()) {
                break;
            }
        }
        
        return ret;
    }
};

2.二分法

    在确定了第一个数a之后我们通过二分法来查找b,使a+b=target,注意因为使用二分法需要排序(会打乱数的排列,题目要求返回下标),因此我们需要构造一个结构体来保存数的下标。时间复杂度降为O(nlog(n))

class Solution {
public:
    struct Node{
        int num;
        int index;
        bool operator<(const struct Node &r) {
            return num < r.num;
        }
    };
    
    int search(vector<Node>& nums, int l, int r, int num) { //在l - r中寻找num
        int res = -1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(nums[mid].num == num) {
                res = nums[mid].index;
                break;
            }else if(nums[mid].num < num) l = mid + 1;
            else r = mid - 1;
        }
        return res;
    }
    
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<Node> temp;
        vector<int> result;
        for(int i=0; i<nums.size(); i++) {
            temp.push_back(Node{nums[i], i});
        }
        sort(temp.begin(), temp.end());
        for(int i=0; i<temp.size(); i++) {
            int res = search(temp, i+1, nums.size()-1, target-temp[i].num);
            if(res == -1) continue;
            result.push_back(temp[i].index);
            result.push_back(res);
            break;
        }
        return result;
    }
};

3.双指针法

     该方法的步骤如下:

     1.将数组升序排序,然后用两个指针变量i, j分别指向数组的头和尾。

     2.如果当前所指向的数的和大于target,则j=j-1, 如果小于则i=i+1,如果等于则跳出。

     3.重复2直到找到一个解。(题目保证有一个解)

     至于为什么要这么做这里给出一个解释我们考虑样例nums = [2, 7, 11, 15]中找和为18的两个数。首先我们列一个两两数相加表。


image.png


    刚开始i=0, j=3,可以观察到此时两数的和为17,小于18,因此i=i+1,因为i=0行不可能有答案存在,此时i=1, j=3,两数和为22,大于18,所以j=j-1,同样j=3列剩下的数大于18,此时i=1, j=2,找到答案。之所以这样做是因为这个矩阵每行递增,每列递增。这样排序之后找答案的复杂度就降为O(n),但是排序仍然需要O(nlogn),因此总的复杂度为O(nlogn),在实现的时候同样需要Node记录下标。

class Solution {
public:
    struct Node{
        int num;
        int index;
        bool operator<(const struct Node &r) {
            return num < r.num;
        }
    };
    
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<Node> temp;
        vector<int> result;
        for(int i=0; i<nums.size(); i++) {
            temp.push_back(Node{nums[i], i});
        }
        sort(temp.begin(), temp.end());
        //双指针法开始
        int i = 0, j = temp.size()-1;
        while(i < j) {
            if(temp[i].num+temp[j].num>target) j--;
            else if(temp[i].num+temp[j].num<target) i++;
            else {
                result.push_back(temp[i].index);
                result.push_back(temp[j].index);
                break;
            }
        }
        return result;
    }
};

    

发表评论

电子邮件地址不会被公开。 必填项已用*标注