Yuhang He's Blog

Some birds are not meant to be caged, their feathers are just too bright.

Find two nums so that they add up to a specific num

In leetcode practice, one simple practice is that given an array of integers, return the two indices of the two numbers such that they add up to a specific number. For example, a[] = {2, 3, 6, 9} and target = 6, we should return 1, 2(the indices of 3, 6). An intuitive algorithm is to write two for loops, like,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> twoSum( std::vector<int>& nums, int target ){
    vector<int> rst;
    for( int i = 0; i< nums.size() - 1; ++i ){
        for( int j = i + 1; j < nums.size(); j++ ){
            sum=numbers[i]+numbers[j];
            if( nums[i] + nums[j] == target ){
                rst.push_back(i+1);
                rst.push_back(j+1);
                return rst;
            }
        }
    }
    return rst;
}

However, it is of $O(N^2)$ computation complexity, which is unbearable in practice. Yes, a much more fast algorithm is desirable and essential. So, let’s step further and think that what if the array a[] is pre-sorted so that the second for loop is ignorable and the computation complexity callapses into $O(N)$? Sorting an array usually requires $O(\log N)$ complexity\,(like fast sorting). Therefore, pre-sorting the array reduces the complexity to $O(N \cdot \log N)$,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> twoSum( std::vector<int>& nums, int target ){
  vector< int > rst;
  vector< int > nums_sorted = sort( nums );
  int begin = 0;
  int end = nums.size() - 1;
  while( begin < end ){
    if( nums_sorted[ begin ] + nums_sorted[ end ] == target ){
      rst.push_back( begin );
      rst.push_back( end );

      return rst;
    }
    if( nums_sorted[ begin ] + nums_sorted[ end ] > target )
      end--;
    if( nums_sorted[ begin ] + nums_sorted[ end ] < target ){
      begin++;
      end = nums.size() - 1;
    }
  }

  return rst;
}

No, that is not enough. Does the sorting $O(\log N)$ complexity can be further eliminated? Remember that the retrieval complexity of harsh table is $O(1)$, why not first storing those numbers into a harsh table so that the overal complexity is reduced to $O(N)$.