# Array and String

###### tags: `LeetCode筆記`

## :memo: 一、1D Array

Most programming languages offer built-in **dynamic array** which is still a random access list data structure but with variable size. For example, we have **vector in C++** and **ArrayList in Java**.

## :memo: Find Pivot Index (Easy)

### 作法 prefix sum
先算總和 sum = Σnums[i]
leftsum: 慢慢從第1項加

1.檢查leftsum是否等於(sum-leftsum)-nums[i]
2.沒有的話就繼續把nums[i]加到leftsum身上leftsum+=nums[i]
**i就是pivot回傳值**
**pivot是不算在等式某一邊的比較對象，比的只有leftsum和sum-leftsum**

這個作法是**O(N)**，很聰明又數學的做法，我沒有想到這個做法，反而還想一個錯誤又複雜的演算法去解，要注意**別複雜化問題!!**
後來才知道根本就是prefix sum啊...

### 作法 C++

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = 0;
        int leftsum = 0;
        
        for (int i = 0;i < nums.size(); i++) {
            sum += nums[i];
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (leftsum == (sum - leftsum) - nums[i]) {
                return i;
            }
            leftsum += nums[i];
        }
        
        return -1;
    }
};

## :memo: Large Number At Least Twice of Others (Easy)

### 作法
第一次for迴圈找出最大後，第二次for迴圈看有沒有*2大於最大的數字，回傳-1

## :memo: Plus One (Easy)

### 作法 C
**step1.** 先檢查(從個位數到最高位數)有沒有9(有就要歸0)因為9+1=10
**step2.** 判斷有沒有走到最高位
**step2-1.** 最高位<9: 最高位+1,returnsize-1並回傳old array
**step2-2.** 最高位=9: 最高位歸0,加一個進位1在最高位左邊,分配new array最高位裝1剩餘位數用old array,並回傳new array
**step3.** 沒有到最高位: 走到哪位後+1並回傳old array

int* plusOne(int* digits, int digitsSize, int* returnSize) {
    int alloc_size = digitsSize+1;
    
    while (digits[digitsSize - 1] == 9 && digitsSize - 1 != 0)
    {
        digits[digitsSize - 1] = 0;
        digitsSize--;
    }
    
    if (digitsSize - 1 == 0)
    {
        if (digits[0] < 9)
        {
            digits[0]++;
            *returnSize = alloc_size - 1;
            
            return digits;
        }
        else
        {
            digits[0] = 0;
            int* newArray = (int*) malloc(sizeof(int) * alloc_size);
            newArray[0] = 1;
            for (int i = 1; i < alloc_size; i++)
            {
                newArray[i] = digits[i - 1];
            }
            *returnSize = alloc_size;
            
            return newArray;
        }
    }
 
    digits[digitsSize - 1]++;
    *returnSize = alloc_size - 1;
    
    return digits;
}

### 作法 C++

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for (int i = digits.size() - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        vector<int> ans(digits.size() + 1, 0);
        ans[0] = 1;
        return ans;
    }
};

## :memo: 二、2D Array
The picture below shows the actual structure of a **M * N** array A:

## :memo: Diagonal Traverse (Medium)


這題數學搞得我好亂，於是看solution後發現:
1.direction在2D Array的好用
2.三元運算子的好閱讀性

### 作法 C++
r和c是列和行，
up = true代表往右上，up = false代表往左下，
往右上直到r == 0或c == n - 1，如果到第n - 1行就往下一列，沒有就往右一行，
往左下直到r == m - 1或c == 0，如果到第m - 1列就往右一行，沒有就往下一列，
up變換方向，up = !up

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        vector<int> a;
        int r = 0, c = 0;
        int m = mat.size(), n = mat[0].size();
        bool up = true;
        while (r < m && c < n) {
            if (up) {
                while (r > 0 && c < n - 1) {
                    a.push_back(mat[r][c]);
                    r--;
                    c++;
                }
                a.push_back(mat[r][c]);
                if (c == n - 1) {
                    r++;
                }
                else {
                    c++;
                }
            }
            else {
                while (r < m - 1 && c > 0) {
                    a.push_back(mat[r][c]);
                    r++;
                    c--;
                }
                a.push_back(mat[r][c]);
                if (r == m - 1) {
                    c++;
                }
                else {
                    r++;
                }
            }
            up = !up;
        }
        return a;
    }
};

## :memo: Spiral Matrix (Medium)


這題因為學會了之前在**Diagonal Traverse**的**direction**用法，加**Mark[10][10]**(拜訪過)，所以寫起來很輕鬆
**[row][column],direction**上下左右跟打電動一樣

### 作法 C

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    int row = 0, column = 0;
    int r = 0;
    int direction = 0;  // 0:right 1:down 2:left 3:up    
    
    *returnSize = matrixSize * (*matrixColSize);
    int* ret = (int*) malloc(sizeof(int) * (*returnSize));
    
    int Mark[10][10] = {0};
    
    // int** Mark = (int**) malloc(sizeof(int*) * matrixSize);
    // for (int i = 0; i < matrixSize; i++)
    // {
    //     Mark[i] = (int*) malloc(sizeof(int) * (*matrixColSize));
    //     for (int j = 0; j < *matrixColSize; j++)
    //     {
    //         Mark[i][j] = 0;
    //     }
    // }
    
    while (r < *returnSize)
    {
        if (direction % 4 == 0 && Mark[row][column] == 0)
        {
            ret[r] = matrix[row][column];
            Mark[row][column] = 1;
            column++;
        }
        else if (direction % 4 == 1 && Mark[row][column] == 0)
        {
            ret[r] = matrix[row][column];
            Mark[row][column] = 1;
            row++;
        }
        else if (direction % 4 == 2 && Mark[row][column] == 0)
        {
            ret[r] = matrix[row][column];
            Mark[row][column] = 1;
            column--;
        }
        else if (direction % 4 == 3 && Mark[row][column] == 0)
        {
            ret[r] = matrix[row][column];
            Mark[row][column] = 1;
            row--;
        }
        
        // 轉彎
        if (column == *matrixColSize || row == matrixSize || column < 0 || Mark[row][column] == 1)
        {
            if (direction % 4 == 0)
            {
                column--;
                row++;
            }
            else if (direction % 4 == 1)
            {
                row--;
                column--;
            }
            else if (direction % 4 == 2)
            {
                column++;
                row--;
            }
            else if (direction % 4 == 3)
            {
                row++;
                column++;
            }
            direction++;
        }
        r++;
    }

    return ret;
}

### 作法 C++

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int sr = 0, sc = 0, er = matrix.size(), ec = matrix[0].size();
        vector<int> ans;
        while (sr < er && sc < ec) {
            for (int i = sc; i < ec; i++) {
                ans.push_back(matrix[sr][i]);
            }
            sr++;
            for (int i = sr; i < er; i++) {
                ans.push_back(matrix[i][ec - 1]);
            }
            ec--;
            cout<<"SR: "<<sr<<"EC: "<<ec<<endl;
            if (sr >= er || sc >= ec) {
                break;
            }
            for (int i = ec - 1; i >= sc; i--) {
                ans.push_back(matrix[er - 1][i]);
            }
            er--;
            for (int i = er - 1; i >= sr; i--) {
                ans.push_back(matrix[i][sc]);
            }
            sc++;
            cout<<"eR: "<<er<<"sC: "<<sc<<endl;
        }
        return ans;
    }
};

### 作法 Set Up Boundaries

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        int up = 0;
        int left = 0;
        int right = n - 1;
        int down = m - 1;
        vector<int> res;
                
        while (res.size() < m * n) {
            // －－>
            for (int col = left; col <= right; col++) {
                res.push_back(matrix[up][col]);
            }
            // ︳
            // ︳
            // ｖ
            for (int row = up + 1; row <= down; row++) {
                res.push_back(matrix[row][right]);
            }
            if (up != down) {
                // <－－
                for (int col = right - 1; col >= left; col--) {
                    res.push_back(matrix[down][col]);
                }
            }
            if (left != right) {
                // ︿
                // ︳
                // ︳
                for (int row = down - 1; row > up; row--) {
                    res.push_back(matrix[row][left]);
                }
            }
            left++;
            right--;
            up++;
            down--;
        }
        
        return res;
    }
};

## :memo: 三、String
#### C
size_t ***strlen**(char *str) //without '\0'
char ***strstr**(char *str, char *srch_term) //回傳term的位址
char ***strcpy**(char *str1, char *str2) //複製字串到str1

#### C++
整數轉字串:
to_string(int)

## :memo: Add Binary (Easy)

**XOR問題**: Single Number II, Single Number III, Maximum XOR of Two Numbers in an Array, Repeated DNA Sequences, Maximum Product of Word Lengths, etc.

### 作法 C
先決定誰是最長位數並分配給ret (size+1)大小的memory，用flag=0/1去看a/b誰長，然後4個if(00,01,10,11)去做運算並記carry是多少，因為是字串，**'\0'也要分配1個char大小的記憶體**

char carry[1] = {'0'}; //{}要寫

ret[retsize] = '\0';

### 作法 Bit Manipulation Java

import java.math.BigInteger;
class Solution {
    public String addBinary(String a, String b) {
        BigInteger x = new BigInteger(a, 2);
        BigInteger y = new BigInteger(b, 2);
        BigInteger zero = new BigInteger("0", 2);
        BigInteger carry, answer;
        while (y.compareTo(zero) != 0) {
          answer = x.xor(y);
          carry = x.and(y).shiftLeft(1);
          x = answer;
          y = carry;
        }
        return x.toString(2);
    }
}

### 作法 Bit-by-Bit Computation C++

class Solution {
public:
    string addBinary(string a, string b) {
        int i = a.length() - 1;
        int j = b.length() - 1;
        string ans;
        int carry = 0;
        
        while (i >= 0 || j >= 0 || carry) {
            if (i >= 0) {
                carry += a[i] - '0';
                i--;
            }
            if (j >= 0) {
                carry += b[j] - '0';
                j--;
            }
            
            ans += (carry % 2 + '0');   // 2 is the number which decides the value of the bit of ans and the value of the next bit of carry
            carry = carry / 2;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

## :memo: Implement strStr (Easy)

### 作法 範例 C

int i,j;
bool found = false;
for (i = 0; haystack[i]; i++)
{
    for (j = 0; needle[j] && haystack[i + j] == needle[j]; j++)
    if (!needle[j])
    {
        found = true;
        break;
    }
}
if (found)
{
    return i;
}
else
{
    return -1;
}

### 作法 C++
有一個函數:
return **haystack.find**(needle);

## :memo: Longest Common Prefix (Easy)

### 作法
以第1個字串做基準依序去和接下來的字串比較並存temp為當下最長匹配字串

這題跟ip-lookup是一樣的概念，solution有很多作法，我比較有興趣的是binary-search，因為跟我之前做的hash-binary search ip-lookup略同，"沒辦法實作C的Hash table"，要找時間去學

### 作法 C++

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int ans = strs[0].length();
        int n = strs.size();
        for (int i = 1; i < n; i++) {
            int j = 0;
            while (j < strs[i].length() && strs[i][j] == strs[0][j]) {
                j++;
            }
            ans = min(ans, j);
        }
        return strs[0].substr(0, ans);
    }
};

## :memo: *Reverse String (Easy)

**基本題**
**時間: O(N/2)**

### 作法 Two pointers

class Solution {
public:
    void reverseString(vector<char>& s) {
        int i = 0;
        int j = s.size() - 1;
        char temp;
        
        for (i = 0; i < s.size() / 2; i++) {
            temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            j--;
        }
    }
};

C++有一個函數:
**reverse**(s.begin(), s.end());

## :memo: *Reverse String II (Easy)
Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.


### 作法

class Solution {
public:
    string reverseStr(string s, int k) {
        
        for (int start = 0; start < s.length(); start += 2 * k) {
            int i = start;
            int j = min(start + k - 1, (int) s.length() - 1);

            while (i < j) {
                char tmp = s[i];
                s[i++] = s[j];
                s[j--] = tmp;
            }
        }

        return s;
    }
};

## :memo: Valid Palindrome (Easy)
A phrase is a **palindrome** if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a **palindrome**, or false otherwise.


### 作法 call c++ function
**isalnum()**:
這個函數返回非零值，如果c是一個數字或字母，否則為0

class Solution {
public:
    bool isPalindrome(string s) {
        for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
        while (i < j && !isalnum(s[i]))
            i++;
        while (i < j && !isalnum(s[j]))
            j--;

        if (tolower(s[i]) != tolower(s[j]))
            return false;
        }

        return true;
    }
};

## :memo: String to Integer (atoi) (Medium)
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

1. Read in and ignore any leading whitespace.
2. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
4. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
5. If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
6. Return the integer as the final result.

Note:

* Only the space character ' ' is considered a whitespace character.
* Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.


### 作法 Follow the Rules
**isdigit()**:
A value different from zero (i.e., true) if indeed c is a decimal digit. Zero (i.e., false) otherwise.

class Solution {
public:
    int myAtoi(string s) {
        int sign = 1;
        int result = 0;
        int index = 0;
        int n = s.size();

        while (index < n and s[index] == ' ') {
            index++;
        }

        if (index < n and s[index] == '+') {
            sign = 1;
            index++;
        } else if (index < n and s[index] == '-') {
            sign = -1;
            index++;
        }

        while (index < n and isdigit(s[index])) {
            int digit = s[index] - '0';

            // Check overflow and underflow conditions.
            if ((result > INT_MAX / 10) or (result == INT_MAX / 10 and digit > INT_MAX % 10)) {
                return sign == 1 ? INT_MAX : INT_MIN;
            }

            result = result * 10 + digit;
            index++;
        }

        return sign * result;
    }
};

## :memo: Array Partition I (Easy)

### 作法 Sorting
**時間: O(NlogN)**
**空間: O(N)**
先sorting後挑偶數項加總

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        // Sort the list in ascending order
        sort(nums.begin(), nums.end());
        // Initialize sum to zero
        int maxSum = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            // Add every element at even positions (0-indexed)
            maxSum += nums[i];
        }
        return maxSum;
    }
};

### 作法 Counting Sort
**時間: O(N+K)** N elements in nums, K = 10000
**空間: O(K)**

class Solution {
public:
    const static int K = 10000;
        
    int arrayPairSum(vector<int>& nums) {
        // Store the frequency of each element
        int elementToCount[2 * K + 1] = {0};
        for (int element : nums) {
            // Add K to element to offset negative values
            elementToCount[element + K]++;
        }
        
        // Initialize sum to zero
        int maxSum = 0;
        bool isEvenIndex = true;
        for (int element = 0; element <= 2 * K; element++) {
            while (elementToCount[element]) {
                // Add element if it is at even position
                maxSum += (isEvenIndex ? element - K : 0);
                // Flip the value (one to zero or zero to one)
                isEvenIndex = !isEvenIndex;
                // Decrement the frequency count
                elementToCount[element]--;
            }
        }
        return maxSum;
    }
};

## :memo: Remove Element (Easy)

### 作法 Two pointers ->->

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0;
        int k = 0;
        
        for (i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                nums[k] = nums[i];
                k++;
            }
        }
        
        return k;
    }
};

## :memo: Max Consecutive Ones (Easy)

### 作法
一直紀錄並更新最長連續1有多長，到底再檢查最後一次

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int count = 0;
        int max_cons = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 1) {
                count++;
            }
            else {
                max_cons = max(max_cons, count);
                count = 0;
            }
        }
        max_cons = max(max_cons, count);
        
        return max_cons;
    }
};

## :memo: 四、Two Sum題型

## 1. Two Sum (Easy)
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have **exactly one solution**, and you may not use the same element twice.

You can return the answer in any order.

### 作法 One-pass Hash Table

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        
        for (int i = 0; i < nums.size(); i++) {
            if (mp.find(target - nums[i]) != mp.end()) {
                return {i, mp[target - nums[i]]};
            }
            mp[nums[i]] = i;
        }
        
        return {};
    }
};

## 2. Two Sum II - Input array is sorted (Medium)

Google範例Interview白板題 喜歡的影片

### 作法 Two pointers
因為已經排序好，所以用兩個pointer，一個在頭，一個在尾，相加相等就break，大於target就尾巴--，小於target就頭++

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i = 0;
        int j = numbers.size() - 1;
        vector<int> ans;
        
        while (true) {
            if (numbers[i] + numbers[j] == target) {
                break;
            }
            else if (numbers[i] + numbers[j] > target) {
                j--;
            }
            else {
                i++;
            }
        }
        
        ans.push_back(i + 1);
        ans.push_back(j + 1);
        
        return ans;
    }
};

## 3. Two Sum III - Data structure design (Easy)
Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.

Implement the TwoSum class:

* TwoSum() Initializes the TwoSum object, with an empty array initially.
* void add(int number) Adds number to the data structure.
* boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.


### 作法

class TwoSum {
    unordered_map<int, int> hash;
public:
    TwoSum() {
        
    }
    
    void add(int number) {
        hash[number]++;
    }
    
    bool find(int value) {
        for (auto h : hash) {
            long val = value;
            if (val == h.first * 2) {
                if (h.second >= 2) return true;
            } else {
                if (hash.find(val - h.first) != hash.end()) return true;
            }
        }
        return false;
    }
};

## 4. Two Sum IV - Input is a BST (Easy)
Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.


### 作法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode *root, vector<int>&ans) {
        if (root == NULL) {
            return;
        }
            
        inorder(root->left, ans);
        ans.push_back(root->val);
        inorder(root->right, ans);
    }
    bool findTarget(TreeNode* root, int k) {
        vector<int>ans;
        inorder(root, ans);
        
        int i = 0;
        int j = ans.size()-1;
        
        while (i < j) {
            if (ans[i] + ans[j] == k) {
                return true;
            }                
            else if (ans[i] + ans[j] < k) {
                i++;
            }                
            else {
                j--;
            }                
        }
        
        return false;
    }
};

## 5. Two Sum BSTs (Medium)
Given the roots of two binary search trees, root1 and root2, return true if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.


### 作法 C++

class Solution {
public:
    void Inorder_traverse(TreeNode* root, unordered_map<int, int>& mp) {
        if (root == nullptr) {
            return;
        }

        if (root->left != nullptr) {
            Inorder_traverse(root->left, mp);
        }

        mp[root->val] = 1;

        if (root->right != nullptr) {
            Inorder_traverse(root->right, mp);
        }
    }

    bool Inorder_traverse_B(TreeNode* root, unordered_map<int, int>& mp, int target) {
        if (root == nullptr) {
            return false;
        }

        bool res = false;
        if (root->left != nullptr) {
            if (Inorder_traverse_B(root->left, mp, target)) {
                res = true;
            }
        }

        if (mp.find(target - root->val) != mp.end()) {
            return true;
        }

        if (root->right != nullptr) {
            if (Inorder_traverse_B(root->right, mp, target)) {
                res = true;
            }
        }

        if (res == true) {
            return true;
        }

        return res;
    }

    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        unordered_map<int, int> mp;

        Inorder_traverse(root1, mp);
        return Inorder_traverse_B(root2, mp, target);        
    }
};

## 6. Two Sum Less Than K (Easy)
Given an array nums of integers and integer k, return the maximum sum such that there exists i < j with nums[i] + nums[j] = sum and sum < k. If no i, j exist satisfying this equation, return -1.


### 作法 Brute Force
**時間O(n^2)**
**空間O(1)**

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        int res = INT_MIN;

        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] < k) {
                    res = max(res, nums[i] + nums[j]);
                }
            }
        }

        return res == INT_MIN ? -1 : res;
    }
};

### 作法 Two Pointers
**時間O(nlogn)**
**空間O(logn)**

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int answer = -1;
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum < k) {
                answer = max(answer, sum);
                left++;
            } else {
                right--;
            }
        }
        return answer;
    }
};

### 作法 Binary Search
**時間O(nlogn)**
**空間O(logn)**

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        int answer = -1;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() && nums[i] < k; i++) {
            auto j = lower_bound(nums.begin() + i + 1, nums.end(), k - nums[i]) - nums.begin() - 1;
            if (j > i) {
                answer = max(answer, nums[i] + nums[j]);
            }
        }
        return answer;
    }
};

### 作法 Counting Sort
**時間O(n+m)**
**空間O(m)**

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        int answer = -1;
        int count[1001] = {};
        for (int num : nums) {
            count[num]++;
        }
        int lo = 1;
        int hi = 1000;
        while (lo <= hi) {
            if (lo + hi >= k || count[hi] == 0) {
                hi--;
            } else {
                if (count[lo] > (lo < hi ? 0 : 1)) {
                    answer = max(answer, lo + hi);
                }
                lo++;
            }
        }
        return answer;
    }
};

## 7. 3Sum (Medium)
Given an integer array nums, return all the triplets **[nums[i], nums[j], nums[k]]** such that **i != j**, **i != k**, and **j != k**, and **nums[i] + nums[j] + nums[k] == 0**.

Notice that the solution set must not contain duplicate triplets.


### 作法 call SumII
只丟負數的index給SumII，right不移動都是nums.size() - 1

class Solution {
public:
    void twoSumII(vector<int>& nums, int i, vector<vector<int>> &res) {
        int lo = i + 1;
        int hi = nums.size() - 1;
        while (lo < hi) {
            int sum = nums[i] + nums[lo] + nums[hi];
            if (sum < 0) {
                ++lo;
            } else if (sum > 0) {
                --hi;
            } else {
                res.push_back({ nums[i], nums[lo++], nums[hi--] });
                while (lo < hi and nums[lo] == nums[lo - 1]) {
                    ++lo;
                }
            }
        }
    }

    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(begin(nums), end(nums));
        vector<vector<int>> res;

        for (int i = 0; i < nums.size() and nums[i] <= 0; ++i) {
            if (i == 0 or nums[i - 1] != nums[i]) {
                twoSumII(nums, i, res);
            }
        }    

        return res;
    }
};

## 8. 3Sum Smaller (Medium)
Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.


### 作法 Two Pointers
C++是nums.size()，所以一開始要判斷是否大於等於3，否則小於3丟到for會錯誤

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        if (nums.size() < 3) {
            return 0;
        }

        sort(begin(nums), end(nums));        
        int sum = 0;

        for (int i = 0; i < nums.size() - 2; i++) {
            int left = i + 1;
            int right = nums.size() - 1;
            while (left < right) {
                if (nums[left] + nums[right] < target - nums[i]) {
                    sum += (right - left);
                    left++;
                } else {
                    right--;
                }
            }
        }

        return sum;
    }
};

## 9. 3Sum Closet (Medium)
Given an integer array **nums** of length n and an integer **target**, find three integers in **nums** such that the sum is closest to **target**.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.


### 作法 Binary Search
利用二元搜尋不對更新最小差距diff
**時間:O(N^2logN)**

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int diff = INT_MAX;
        int sz = nums.size();
        
        sort(begin(nums), end(nums));

        for (int i = 0; i < sz and diff != 0; ++i) {
            for (int j = i + 1; j < sz - 1; ++j) {
                int complement = target - nums[i] - nums[j];
                auto it = upper_bound(begin(nums) + j + 1, end(nums), complement);
                int hi = it - begin(nums);
                int lo = hi - 1;
                if (hi < sz and abs(complement - nums[hi]) < abs(diff)) {
                    diff = complement - nums[hi];
                }
                if (lo > j and abs(complement - nums[lo]) < abs(diff)) {
                    diff = complement - nums[lo];
                }
            }
        }

        return target - diff;
    }
};

## 10. 3Sum With Multiplicity (Medium)
Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it **modulo** 10^9 + 7.


### 作法 Counting with Cases
數值範圍小所以用count去計數
**時間:O(N+W^2)** N是size，W是最大數值

class Solution {
public:
    int threeSumMulti(vector<int>& arr, int target) {
        int MOD = 1000000007;

        long count[101] = {0};
        for (int x : arr) {
            count[x]++;
        }

        long ans = 0;

        // All different
        for (int x = 0; x <= 100; ++x) {
            for (int y = x + 1; y <= 100; ++y) {
                int z = target - x - y;
                if (y < z and z <= 100) {
                    ans += count[x] * count[y] * count[z];
                    ans %= MOD;
                }
            }
        }

        // x == y != z
        for (int x = 0; x <= 100; ++x) {
            int z = target - 2 * x;
            if (x < z and z <= 100) {
                ans += count[x] * (count[x] - 1) / 2 * count[z];
                ans %= MOD;
            }
        }

        // x != y == z
        for (int x = 0; x <= 100; ++x) {
            if (target % 2 == x % 2) {
                int y = (target - x) / 2;
                if (x < y and y <= 100) {
                    ans += count[x] * count[y] * (count[y] - 1) / 2;
                    ans %= MOD;
                }
            }
        }

        // x == y == z
        if (target % 3 == 0) {
            int x = target / 3;
            if (0 <= x and x <= 100) {
                ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;
                ans %= MOD;
            }
        }

        return (int) ans;
    }
};

## 11. 4Sum (Medium)
Given an array nums of n integers, return an array of all the **unique** quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

* 0 <= a, b, c, d < n
* a, b, c, and d are **distinct**.
* nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in **any order**.


### 作法 Two Pointers

class Solution {
public:
    vector<vector<int>> twoSum(vector<int>& nums, long long target, int start) {
        vector<vector<int>> res;
        int lo = start, hi = int(nums.size()) - 1;

        while (lo < hi) {
            int curr_sum = nums[lo] + nums[hi];
            if (curr_sum < target || (lo > start and nums[lo] == nums[lo - 1])) {
                lo++;
            } else if (curr_sum > target || (hi < nums.size() - 1 and nums[hi] == nums[hi + 1])) {
                hi--;
            } else {
                res.push_back({ nums[lo++], nums[hi--] });
            }
        }

        return res;
    }

    vector<vector<int>> kSum(vector<int>& nums, long long target, int start, int k) {
        vector<vector<int>> res;

        if (start == nums.size()) {
            return res;
        }

        long long average_value = target / k;

        // nums can't meet
        if (nums[start] > average_value || average_value > nums.back()) {
            return res;
        }

        if (k == 2) {
            return twoSum(nums, target, start);
        }

        // static_cast<long long>??
        for (int i = start; i < nums.size(); i++) {
            if (i == start || nums[i - 1] != nums[i]) {
                for (vector<int>& subset : kSum(nums, static_cast<long long>(target) - nums[i], i + 1, k - 1)) {
                    res.push_back({nums[i]});
                    res.back().insert(end(res.back()), begin(subset), end(subset));
                }
            }
        }

        return res;
    }

    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(begin(nums), end(nums));
        return kSum(nums, target, 0, 4);      
    }
};

## 12. 4Sum II (Medium)

### 作法
可以用在kSum II，5Sum II或6Sum II都行，看熟

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        vector<vector<int>> lsts = {nums1, nums2, nums3, nums4};
        int k = int(lsts.size());
        
        auto countSum = [&](int start, int end) {
            map<int, int> cnt({{0, 1}});
            for (int i = start; i < end; i++) {
                map<int, int> temp;
                for (int total : lsts[i]) {
                    for (auto k = cnt.begin(); k != cnt.end(); k++) {
                        temp[total + k->first] += k->second;
                    }
                }
                cnt = temp;
            }
            return cnt;
        };
        
        map<int, int> left = countSum(0, k / 2);
        map<int, int> right = countSum(k / 2, k);
        int res = 0;
        for (auto k = left.begin(); k != left.end(); k++) {
            res += k->second * right[-k->first];
        }
        
        return res;
    }
};

### 作法 HashMap

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        int cnt = 0;
        unordered_map<int, int> m;
        for (int a : A) {
            for (int b : B) {
                ++m[a + b];
            }
        }
        
        for (int c : C) {
            for (int d : D) {
                auto it = m.find(-(c + d));
                if (it != end(m)) {
                    cnt += it->second;
                }
            }    
        }
        return cnt;
    }
};

## :memo: Minimum Size Subarray Sum (Medium)
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is **greater than or equal to** target. If there is no such subarray, return 0 instead.


### 作法
**時間: O(N)**
**空間: O(1)**
用**2個pointer**去跑和**solution approach#4**一樣
pass1 231<7
pass2 2312>7 記4
pass3 31<7
pass4 312<7
pass5 3124>7 記4
pass6 124=7 記3
pass7 24<7
pass8 243>7 記3
pass9 43=7 記2 //回傳2

### 作法 C++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ans = INT_MAX;
        int left = 0;
        int sum = 0;
        
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            while (sum >= target) {
                ans = min(ans, i + 1 - left);
                sum -= nums[left++];
            }
        }
        
        return ans != INT_MAX ? ans : 0;
    }
};

## :memo: Reverse Words in a String (Medium)

### 作法 範例
**時間: O(N)**
**空間: O(N)**

void reverse(char *start,char *end)
{
    while (end > start)
    {
        char temp = *start;
        *start = *end;
        *end = temp;
        start++, end--;
    }
}

void trim(char *S)
{
    int count = 0;
    int N = strlen(S);
    int flag = 1;
    for (int i = 0; i < N; i++)
    {
        if (S[i] != ' ')
        {
            S[count++] = S[i];
            flag = 0;
        }
        else
        {
            if (!flag)
            {
                S[count++] = S[i];
                flag = 1;
            }
        }
    }
    if (count >= 1 && S[count - 1] == ' ')
    {
        S[count - 1] = '\0';
    }        
    else
    {
        S[count] = '\0';
    }        
}

char * reverseWords(char * s){
    trim(s);
    char *temp = s, *prev = s;
    while (*temp)
    {
        temp++;
        if (*temp == ' ')
        {
            reverse(prev, temp - 1);
            prev = temp + 1;
        }
        else if (*temp == '\0')
        {
            reverse(prev, temp - 1);
        }
    }
    reverse(s, temp - 1);

    return s;
}

## :memo: Reverse Words in a String III (Easy)

### 作法 用Reverse Words in a String的範例解法去註解幾行就可以完成

void reverse(char *start,char *end)
{
    while(end > start)
    {
        char temp = *start;
        *start = *end;
        *end = temp;
        start++, end--;
    }
}

void trim(char *S)
{
    int count = 0;
    int N = strlen(S);
    int flag = 1;
    for (int i = 0; i < N; i++)
    {
        if (S[i] != ' ')
        {
            S[count++] = S[i];
            flag = 0;
        }
        else
        {
            if (!flag)
            {
                S[count++] = S[i];
                flag = 1;
            }
        }
    }
    if (count >= 1 && S[count - 1] == ' ')
    {
        S[count - 1] = '\0';
    }        
    else
    {
        S[count] = '\0';
    }        
}

char * reverseWords(char * s) {
    //trim(s);
    char *temp = s, *prev = s;
    while (*temp)
    {
        temp++;
        if (*temp == ' ')
        {
            reverse(prev, temp - 1);
            prev = temp + 1;
        }
        // else if(*temp == '\0')
        // {
        //     reverse(prev, temp - 1);
        // }
    }
    //reverse(s, temp - 1);
    reverse(prev, temp - 1);

    return s;
}

### 作法 Two pointers
**時間: O(N)**
**空間: O(1)**

class Solution {
public:
    string reverseWords(string s) {
        int lastSpaceIndex = -1;
        int len = (int)s.size();
        for (int strIndex = 0; strIndex <= len; strIndex++) {
            if (strIndex == len || s[strIndex] == ' ') {
                // Two pointers: startIndex, endIndex
                int startIndex = lastSpaceIndex + 1;
                int endIndex = strIndex - 1;
                while (startIndex < endIndex) {
                    char temp = s[startIndex];
                    s[startIndex] = s[endIndex];
                    s[endIndex] = temp;
                    startIndex++;
                    endIndex--;
                }
                lastSpaceIndex = strIndex;
            }
        }
        return s;
    };
};

## :memo: Rotate Array (Medium) 比較 Rotate List (Medium)

### 作法 Using Cyclic Replacements
**時間: O(N)**
**空間: O(1)**
count會隨著do-while增加，所以count增加的速度比start還快
**綠紅箭頭交叉前進!**

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        int count = 0;
        for (int start = 0; count < nums.size(); start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % nums.size();
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }
    }
};

### 作法 Using Reverse

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        // reverse all numbers
        reverse(nums.begin(), nums.end());
        // reverse first k numbers
        reverse(nums.begin(), nums.begin() + k);
        // reverse last n - k numbers
        reverse(nums.begin() + k, nums.end());
    }
};

## :memo: Pascal's Triangle (Easy)

### 作法
畫圖想成直角三角形
用nested for loop兩層去完成

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        
        for (int i = 0; i < numRows; i++) {
            vector<int> temp(i + 1, 1);
            if (i <= 1) {
                ans.push_back(temp);
            }
            else {
                for (int j = 1; j <= i - 1; j++) {
                    temp[j] = ans[i - 1][j - 1] + ans[i - 1][j];
                }
                ans.push_back(temp);
            }
        }
        
        return ans;
    }
};

## :memo: Pascal's Triangle II (Easy)

### 作法

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<vector<int>> ans;
        
        for (int i = 0; i <= rowIndex; i++) {
            vector<int> tmp;
            for (int j = 0; j <= i; j++) {
                tmp.push_back(1);
            }
            ans.push_back(tmp);
        }
        
        for (int i = 2; i <= rowIndex; i++) {
            for (int j = 1; j < i; j++) {
                ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
            }
        }
        
        for (auto i: ans) {
            for (auto j: i) {
                cout<<j<<" ";
            }
            cout<<endl;
        }
        
        return ans[rowIndex];
    }
};

## :memo: Increasing Triplet Subsequence (Medium)
Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.


### 作法 Linear Scan

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first = INT_MAX;
        int second = INT_MAX;
        
        // second代表的是一個意義: means前面的index有人比他小
        // 所以只要有n大於second就代表: Triplet成立
        for (int n : nums) {
            if (n <= first) {
                first = n;
            } else if (n <= second) {
                second = n;
            } else {
                return true;
            }
        }
        
        return false;
    }
};

## :memo: 刷題檢討
array題目偏簡單，最後的Reverse Words有點難，要基本會實作字串反轉