資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++ 中的 3Sum Smaller
假設我們有一個名為 nums 的包含 n 個整數的陣列，我們還有一個目標值 target，我們需要找到索引三元組 (i, j, k) 的數量，其中 i、j、k 的範圍都在 0 到 n - 1 之間，並且滿足條件 nums[i] + nums[j] + nums[k] < target。
因此，如果輸入類似於 nums = [-2,0,1,3]，而 target = 2，則輸出將為 2，因為有兩個三元組的和小於 2：[-2,0,1] 和 [-2,0,3]。
為了解決這個問題，我們將遵循以下步驟：
ret := 0
對陣列 a 進行排序
n := a 的大小
對於初始化 i := 0，當 i < n - 2 時，更新（將 i 增加 1），執行：
left := i + 1, right := n - 1
當 left < right 時，執行：
sum := a[i] + a[left] + a[right]
如果 sum < t，則：
ret := ret + right - left
(將 left 增加 1)
否則
(將 right 減小 1)
返回 ret
示例
讓我們看看下面的實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int threeSumSmaller(vector<int<& a, int t) {
int ret = 0;
sort(a.begin(), a.end());
int n = a.size();
for (int i = 0; i < n - 2; i++) {
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = a[i] + a[left] + a[right];
if (sum < t) {
ret += right - left;
left++;
}
else
right--;
}
}
return ret;
}
};
main(){
Solution ob;
vector<int< v = {-2,0,1,3};
cout << (ob.threeSumSmaller(v,2));
}輸入
[-2,0,1,3] 2
輸出
2
更新於：2020-11-18
265 次瀏覽
廣告