Đề bài:
Cho một mảng nums gồm n số nguyên, trả về một mảng chứa tất cả các bộ tứ [nums[a], nums[b], nums[c], nums[d]] duy nhất sao cho:
- 0 <= a, b, c, d < n
- a, b, c, và d là các chỉ số khác nhau.
- nums[a] + nums[b] + nums[c] + nums[d] == target
Bạn có thể trả về kết quả theo bất kỳ thứ tự nào.
Ví dụ 1:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Ví dụ 2:
Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]]
Ràng buộc:
- 1 <= độ dài của mảng nums <= 200
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
Giải thích thuật toán bằng C++
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
vector<int> path;
ranges::sort(nums);
nSum(nums, 4, target, 0, nums.size() - 1, path, ans);
return ans;
}
private:
// Finds n numbers add up to the target in [l, r].
void nSum(const vector<int>& nums, long n, long target, int l, int r,
vector<int>& path, vector<vector<int>>& ans) {
if (r - l + 1 < n || target < nums[l] * n || target > nums[r] * n)
return;
if (n == 2) {
// Similar to the sub procedure in 15. 3Sum
while (l < r) {
const int sum = nums[l] + nums[r];
if (sum == target) {
path.push_back(nums[l]);
path.push_back(nums[r]);
ans.push_back(path);
path.pop_back();
path.pop_back();
++l;
--r;
while (l < r && nums[l] == nums[l - 1])
++l;
while (l < r && nums[r] == nums[r + 1])
--r;
} else if (sum < target) {
++l;
} else {
--r;
}
}
return;
}
for (int i = l; i <= r; ++i) {
if (i > l && nums[i] == nums[i - 1])
continue;
path.push_back(nums[i]);
nSum(nums, n - 1, target - nums[i], i + 1, r, path, ans);
path.pop_back();
}
}
};
Đây là một phương thức trong một lớp được gọi là `Solution`. Phương thức này được sử dụng để tìm tất cả các bộ tứ số trong một mảng `nums` sao cho tổng của chúng bằng một giá trị `target`.
Thuật toán này sử dụng phương pháp đệ quy để giải quyết vấn đề này. Ở mỗi bước đệ quy, thuật toán đang tìm kiếm các cặp số (hoặc bộ số) có thể cộng lại thành `target` trong một phạm vi cụ thể của mảng `nums`. Nếu `n` (số lượng số) bằng 2, thuật toán giống với thuật toán 3Sum.
Dưới đây là cách thuật toán hoạt động:
1. Phương thức `fourSum` nhận đầu vào là một mảng `nums` và giá trị `target`.
2. Tạo ra hai biến `ans` và `path` để lưu trữ kết quả.
3. Sắp xếp mảng `nums` theo thứ tự tăng dần bằng cách sử dụng hàm `ranges::sort`.
4. Gọi phương thức `nSum` để tìm tất cả các bộ tứ số. Truyền vào `nums`, `4` (số lượng số cần tìm), `target`, `0` (vị trí bắt đầu của phạm vi tìm kiếm), `nums.size() – 1` (vị trí kết thúc của phạm vi tìm kiếm), `path` (đường đi hiện tại), và `ans` (kết quả).
5. Trả về kết quả `ans`.
Phương thức `nSum` được sử dụng để tìm các bộ số trong mảng `nums` sao cho tổng của chúng bằng `target`.
Cách hoạt động của phương thức `nSum` như sau:
1. Kiểm tra các điều kiện dừng. Nếu kích thước của phạm vi tìm kiếm (`r – l + 1`) nhỏ hơn `n`, hoặc `target` nhỏ hơn `nums[l] * n`, hoặc `target` lớn hơn `nums[r] * n`, thì dừng lại (không tìm được kết quả).
2. Nếu `n` bằng 2, thực hiện thuật toán tương tự như 3Sum:
– Sử dụng hai con trỏ `l` và `r` để duyệt qua phạm vi từ `l` đến `r`.
– Tính tổng của hai số `nums[l]` và `nums[r]`.
– Nếu tổng bằng `target`, thêm `nums[l]` và `nums[r]` vào `path`, sau đó thêm `path` vào `ans`. Sau đó, loại bỏ `nums[l]` và `nums[r]` từ `path`.
– Tăng `l` và giảm `r` một đơn vị.
– Loại bỏ các phần tử trùng lặp trong mảng.
3. Ngược lại, nếu `n` lớn hơn 2:
– Duyệt qua mảng `nums` từ `l` đến `r`.
– Nếu chỉ số `i` lớn hơn `l` và `nums[i]` bằng `nums[i – 1]`, bỏ qua lần lặp hiện tại để tránh các bộ số trùng lặp.
– Thêm `nums[i]` vào `path`.
– Gọi đệ quy phương thức `nSum` với `n – 1`, `target – nums[i]`, `i + 1`, `r`, `path`, và `ans`.
– Loại bỏ `nums[i]` từ`path`.
Đây là một thuật toán tìm kiếm đệ quy được sử dụng để giải quyết bài toán tìm tất cả các bộ tứ số có tổng bằng một giá trị `target` trong một mảng `nums`. Thuật toán sắp xếp mảng `nums` và sau đó sử dụng phương pháp đệ quy để tìm kiếm tất cả các bộ số thỏa mãn yêu cầu.
Giải thích thuật toán bằng Java
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
nSum(nums, 4, target, 0, nums.length - 1, new ArrayList<>(), ans);
return ans;
}
// Finds n numbers that add up to the target in [l, r].
private void nSum(int[] nums, long n, long target, int l, int r, List<Integer> path,
List<List<Integer>> ans) {
if (r - l + 1 < n || target < nums[l] * n || target > nums[r] * n)
return;
if (n == 2) {
// Similar to the sub procedure in 15. 3Sum
while (l < r) {
final int sum = nums[l] + nums[r];
if (sum == target) {
path.add(nums[l]);
path.add(nums[r]);
ans.add(new ArrayList<>(path));
path.remove(path.size() - 1);
path.remove(path.size() - 1);
++l;
--r;
while (l < r && nums[l] == nums[l - 1])
++l;
while (l < r && nums[r] == nums[r + 1])
--r;
} else if (sum < target) {
++l;
} else {
--r;
}
}
return;
}
for (int i = l; i <= r; ++i) {
if (i > l && nums[i] == nums[i - 1])
continue;
path.add(nums[i]);
nSum(nums, n - 1, target - nums[i], i + 1, r, path, ans);
path.remove(path.size() - 1);
}
}
}
Giải thích thuật toán bằng Python
class Solution:
def fourSum(self, nums: List[int], target: int):
ans = []
def nSum(l: int, r: int, target: int, n: int, path: List[int], ans: List[List[int]]) -> None:
"""Finds n numbers that add up to the target in [l, r]."""
if r - l + 1 < n or n < 2 or target < nums[l] * n or target > nums[r] * n:
return
if n == 2:
while l < r:
summ = nums[l] + nums[r]
if summ == target:
ans.append(path + [nums[l], nums[r]])
l += 1
while nums[l] == nums[l - 1] and l < r:
l += 1
elif summ < target:
l += 1
else:
r -= 1
return
for i in range(l, r + 1):
if i > l and nums[i] == nums[i - 1]:
continue
nSum(i + 1, r, target - nums[i], n - 1, path + [nums[i]], ans)
nums.sort()
nSum(0, len(nums) - 1, target, 4, [], ans)
return ans
0 / 5 - (0 Đánh Giá)