LeetCode #1:Two Sum(两数之和)

题目描述:

思路:

若运用暴力解法,时间复杂度较高。这里运用二分查找法求解。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>index;
        vector<int>numbers=nums;
        sort(numbers.begin(),numbers.end());
        int front=0,rear=(int)numbers.size()-1;
        int sum=0;
        while(front<rear)
        {
            sum = numbers[front] + numbers[rear];
            if(sum==target)
            {
                for(int i=0;i<nums.size();i++)
                {
                    if(index.size()==2)
                        break;
                    if(numbers[front]==nums[i])
                        index.push_back(i);
                    else if(numbers[rear]==nums[i])
                        index.push_back(i);
                }
                break;
            }
            else if(sum<target)
            {
                front++;
            }
            else if(sum>target)
            {
                rear--;
            }
        }
        return index;
    }
};

发表评论

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