Leetcode has several related sum-of-two problems, summarized here as follows.

1. # 1The Sum of Two numbers

1.1 the original topic

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].
Copy the code

1.2 solution

1.2.1 Iterative method of violence

The first method that came to mind was the iterative method, which traversed the number group from [0,n-1] to nums[I], and searched nums[I +1,n-1] that met the conditions. The code is O(n^2). It’ll pass, but it’ll take a lot of time.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        for(int i=0; i<nums.size()- 1; i++)for(int j=i+1; j<nums.size(); j++) {if(target==nums[i]+nums[j]) { result.push_back(i); result.push_back(j); }}returnresult; }};Copy the code

1.2.2 Hash table

To be perfect. I’m not familiar with hash tables.

Blog park blogger Grandyang’s solution to the problem

2. # 167Two Sum II – Input array is sorted

2.1 the original topic

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

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.
Copy the code

2.2 solution

Blog Park blogger Grandyang’s description

This is another derivative of Two Sum, and as the beginning of LeetCode, we must solve Two Sum and all the derivatives. This problem should be easier, because the given array is ordered, and the problem limits that there must be a solution. The first method I thought of was to search by dichotomy.

This is the title of LeetCode’s Arrays and Strings section, which deals with the two-pointer technique and is part of the two-pointer scenario 1. The summary of scenario 1 is as follows:

Anyway, one of the typical scenarios for using the two-pointer technique is when you want to iterate through an array from both ends to the middle. Here you can use the two-pointer technique: one pointer starts at the beginning and the other pointer starts at the end. It’s worth noting that this technique is often used in array sorting.

2.2.1 dichotomy

When I did it myself, my first thought was also dichotomy (though I didn’t know it was called dichotomy at the time), which didn’t use the two-pointer technique of iterating from both ends to the middle. Own code as follows, complexity O(NLGN) :

//O(nlgn)
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int count=numbers.size();
        if(count<=1)
            return {};
        bool find=false;
        vector<int> res;
        for(int i=0; i<count- 1; i++) {int start=i+1;
            int end=count- 1;
           
            while(start<=end&&find==false)
            {
                int center=(start+end)/2;
                int tmp=numbers[i]+numbers[center];
                if(tmp>target)
                {
                    end=center- 1;
                }
                else if(tmp<target)
                {
                    start=center+1;
                }
                else
                {
                    find=true;
                    res.push_back(i+1);
                    res.push_back(center+1); }}if(find)
                break;
        }
        returnres; }};Copy the code

2.2.2 Dual-pointer Technique (Colliding Pointers)

This method uses the two-pointer technique,

Anyway, one of the typical scenarios for using the two-pointer technique is when you want to iterate through an array from both ends to the middle. Here you can use the two-pointer technique: one pointer starts at the beginning and the other pointer starts at the end. It’s worth noting that this technique is often used in array sorting.

We only need two Pointers, a pointer to the beginning, and a pointer to the end, and then to the middle of traverse, if the two Numbers to add exactly equal to the target, to return to the position of the two Pointers can be directly, if less than the target, the left pointer moves to the right one, if it is greater than the target, pointer moves left a right and so on until meet two Pointers to stop. The code is O(n).

// O(n)
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0, r = numbers.size() - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) return {l + 1, r + 1};
            else if (sum < target) ++l;
            else --r;
        }
        return{}; }};Copy the code

#3.# Two Sum III – Data structure Design