題目鏈接：18. 四數之和 - 力扣（LeetCode）
普通版本（排序 + 雙指針）
主旨：類似于三數之和的解法，但需要多加一些限制，同時為了防止多個數組元素的相加之和出現整型溢出問題還要將整型轉為long
補充：(long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3]?是表達式的類型提升，有一個long則后面的所有運算均提升為long操作?
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> quadruplets;if (nums.size() < 4) {return quadruplets;}sort(nums.begin(), nums.end());int length = nums.size();for (int i = 0; i < length - 3; i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {break;}if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {continue;}for (int j = i + 1; j < length - 2; j++) {if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {break;}if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {continue;}int left = j + 1, right = length - 1;while (left < right) {long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];if (sum == target) {quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]});while (left < right && nums[left] == nums[left + 1]) {left++;}left++;while (left < right && nums[right] == nums[right - 1]) {right--;}right--;} else if (sum < target) {left++;} else {right--;}}}}return quadruplets;}
};時間復雜度：O（N^3）（查找前兩個數要兩次for，查找后兩個數因為有雙指針同時向里走的緣故，所以只用一層for）
空間復雜度：O（log n） （仍然是花費在了排序的額外空間上）
優化版本（待補充）
~over~
)
)
