# Leetcode刷題學習筆記 -- Two-Pointers Binary Search
## Introduction
問題: 在一個vector<int>中，找出兩個element的和為target。

最直覺的解法是暴力破解。

vector<int> nums{1, 3, 5, 2, 4, 6};
int target = 6;
int ans = 0;
for(int i = 0; i < nums.size(); ++i) {
    for(int j = i + 1; j < nums.size(); ++j) {
        if(nums[i] + nums[j] == target)
            return {i, j};
    }                               
}

其中 time complexity : $O(N^2)$，效果不是很好。
仔細觀察所有2 sum的組合為

{1, 3, 5, 2, 4, 6} --sort--> {1, 2, 3, 4, 5, 6}
    
{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}
        {2, 3}, {2, 4}, {2, 5}, {2, 6}
                {3, 4}, {3, 5}, {3, 6}
                        {4, 5}, {4, 6}
                                {5, 6}
    
{3, 4, 5, 5, 6, 6, 7, 7, 7, 8, 8, 9, 9, 10, 11}

當我們對vector<int> nums排序後，我們就可以從結果的中間值開始搜尋，從上面的例子來看就是7。

                                 
{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6} <-{i, j}
        {2, 3}, {2, 4}, {2, 5}, {2, 6}
                {3, 4}, {3, 5}, {3, 6}
                        {4, 5}, {4, 6}
                                {5, 6}
    
{3, 4, 5, 5, 6, 6, 7, 7, 7, 8, 8, 9, 9, 10, 11}
                     /|\
                      |

我們從中間值開始找，如果要找的值比target還大，那就移動i往上尋找，如果比target還小那就移動j往下尋找。

ex：移動i往大的值尋找

                                 
{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6} 
        {2, 3}, {2, 4}, {2, 5}, {2, 6} <-{i, j}
                {3, 4}, {3, 5}, {3, 6}
                        {4, 5}, {4, 6}
                                {5, 6}
    
{3, 4, 5, 5, 6, 6, 7, 7, 7, 8, 8, 9, 9, 10, 11}
                              /|\
                               |

ex：移動j往小的值尋找

                                 
{1, 2}, {1, 3}, {1, 4}, {1, 5},<-{i, j} {1, 6} 
        {2, 3}, {2, 4}, {2, 5},         {2, 6} 
                {3, 4}, {3, 5},         {3, 6}
                        {4, 5},         {4, 6}
                                        {5, 6}
    
{3, 4, 5, 5, 6, 6, 7, 7, 7, 8, 8, 9, 9, 10, 11}
               /|\
                |

所以程式碼可以如下

vector<int> nums{1, 3, 5, 2, 4, 6};
sort(nums.begin(), nums.end());
int i = 0, j = nums.size() - 1;
while(i < j) {
    if(nums[i] + nums[j] > target) --j;
    else if(nums[i] + nums[j] < target) ++i;
    else { // 找到一組這樣的組合
        rtn.push_back({nums[i], nums[j]});
        i++;  // 往左斜下尋找
        j--;
    }
}
return {-1, -1}; // 找不到這樣的組合

或是使用下面的方法

for(int i = 0, j = nums.size() - 1; i < j; ++i) {
    while(i < j && nums[i] + nums[j] >= target){ 
        if(nums[i] == nums[j] == target) 
            rtn.push_back({nums[i], nums[j]});
        --j;
    }
}

另一種題目的問法是，找出小於等於target的組合數。
這時候可以用以下的方法。

for(int i = 0, j = nums.size() - 1; i < j; ++i) {
    while(i < j && nums[i] + nums[j] > target)
        --j;
    ans += j - i;
}

## Problems
### [2563. Count the Number of Fair Pairs](https://leetcode.com/problems/count-the-number-of-fair-pairs/description/)
找出滿足
1. 0<=i<j<nums.size()，
2. lower <= nums[i] + nums[j] <= upper
所以有的組合數。

class Solution {
    long long countLess(vector<int>& nums, int target) {
        long long ans{0};
        for(int i = 0, j = nums.size() - 1; i < j; ++i) {
            while(i < j && nums[i] + nums[j] > target) --j;
            ans += j - i;
        } 
        return ans;
    }
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        return countLess(nums, upper) - countLess(nums, lower - 1);
    }
};

###### tags: `leetcode` `刷題`