DEV Community

1 2

K Sum - Two Pointers

Two Sum

https://leetcode.com/problems/two-sum/

Greedy

class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    const int n = nums.size();
    for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
        if (nums[i] + nums[j] == target) {
          return vector<int>{i, j};
        }
      }
    }
    throw "no combination";
  }
};

Hash Table

class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    const int n = nums.size();
    unordered_map<int, int> m;
    for (int i = 0; i < n; i++) {
      const int complement = target - nums[i];
      if (m.find(complement) != m.end()) {
        return vector<int>{m[complement], i};
      }
      m[nums[i]] = i;
    }
    throw "no combination";
  }
};

Two Sum II - Input array is sorted

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

class Solution {
 public:
  vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0;
    int r = numbers.size() - 1;
    while (l < r) {
      const int sum = numbers[l] + numbers[r];
      if (sum == target) {
        return vector<int>{l + 1, r + 1};
      } else if (sum < target) {
        l++;
      } else {
        r--;
      }
    }
    throw "no combination";
  }
};

3Sum

https://leetcode.com/problems/3sum/

class Solution {
  int twoSumSmaller(vector<int> &nums, int start, int target) {
    int count = 0;
    int l = start;
    int r = nums.size() - 1;
    while (l < r) {
      int sum = nums[l] + nums[r];
      if (sum >= target) {
        r--;
        continue;
      }
      count += r - l;
      l++;
    }
    return count;
  }

 public:
  int threeSumSmaller(vector<int> &nums, int target) {
    int count = 0;
    sort(nums.begin(), nums.end());
    const int n = nums.size();
    for (int i = 0; i < n; i++) {
      count += twoSumSmaller(nums, i + 1, target - nums[i]);
    }
    return count;
  }
};

4Sum

https://leetcode.com/problems/4sum/

class Solution {
  vector<vector<int>> kSum(vector<int> &nums, int k, int start, int target) {
    const int n = nums.size();
    vector<vector<int>> results;
    if (k == 2) {
      // two sum
      int l = start;
      int r = n - 1;
      while (l < r) {
        const int sum = nums[l] + nums[r];
        if (sum < target || (start < l && nums[l] == nums[l - 1])) {
          l++;
        } else if (target < sum || (r < n - 1 && nums[r] == nums[r + 1])) {
          r--;
        } else {
          results.push_back(vector<int>{nums[l], nums[r]});
          l++;
          r--;
        }
      }
      return results;
    }
    for (int i = start; i <= n - k; i++) {
      if (i > start && nums[i - 1] == nums[i]) {
        continue;
      }
      for (auto result : kSum(nums, k - 1, i + 1, target - nums[i])) {
        result.insert(result.begin(), nums[i]);
        results.push_back(result);
      }
    }

    return results;
  }

 public:
  vector<vector<int>> fourSum(vector<int> &nums, int target) {
    sort(nums.begin(), nums.end());
    auto results = kSum(nums, 4, 0, target);
    return results;
  }
};

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more