leetcode

0 // Brute force

1 class Solution {

2 public:

3 int countPairs(const vector<int> &nums, int target) const {

4 const int n = size(nums);

5 int res = 0;

6

7 for (int i = 0; i < n; i++) {

8 for (int j = 0; j < i; j++) {

9 res += nums[i] + nums[j] < target;

10 }

11 }

12

13 return res;

14 }

15 };

16

17 // Two pointer

18 class Solution {

19 public:

20 int countPairs(vector<int> &nums, int target) const {

21 int i = 0, j = size(nums) - 1;

22 int res = 0;

23

24 sort(begin(nums), end(nums));

25 while (i < j) {

26 if (nums[i] + nums[j] < target)

27 res += j - i, i++;

28 else

29 j--;

30 }

31

32 return res;

33 }

34 };