C++ solution, binary search and two pointers


  • 0
    X
    class Solution {
    public:
        vector<int> twoSum(vector<int>& numbers, int target) {
          int low = 0, high = numbers.size() - 1;
          while (low < high) {
            if (numbers[low] + numbers[high] == target) {
              return {low + 1, high + 1};
            } 
            
            numbers[low] + numbers[high] < target ? low++ : high--;
          }
          return vector<int>();
        }
    };
    
    class Solution {
    public:
      vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0; i < numbers.size() - 1; i++) {
          int index = binarySearch(numbers, i + 1, numbers.size() - 1, target - numbers[i]);
          if (index != -1) return {i + 1, index + 1};
        }
      }
      
      int binarySearch(vector<int>& numbers, int begin, int end, int des) {
        int l = begin, r = end;
        while (l <= r) {
          int mid = (l + r) / 2;
          if (des == numbers[mid]) return mid;
          if (des < numbers[mid]) {
            r = mid - 1;
          } else {
            l = mid + 1;
          }
        }
        return -1;
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.