Cách tiếp cận dễ dàng là chúng ta có thể tạo ba vòng lặp lồng nhau và lần lượt kiểm tra xem tổng của cả ba phần tử có bằng 0 hay không. Nếu tổng của ba phần tử bằng 0 thì in các phần tử.
Độ phức tạp về thời gian - O (n 3 )
Độ phức tạp của không gian - O (1)
Chúng ta có thể sử dụng cấu trúc dữ liệu tập hợp không có thứ tự để lưu trữ từng giá trị của mảng. Tập hợp cung cấp lợi ích của việc tìm kiếm một phần tử trong thời gian O (1). Vì vậy, đối với mỗi cặp trong mảng, chúng ta sẽ tìm số âm của tổng của chúng có thể tồn tại trong tập hợp. Nếu một phần tử như vậy được tìm thấy thì chúng ta có thể in ra bộ ba là cặp số nguyên và giá trị âm của tổng của chúng.
Độ phức tạp về thời gian - O (n 2 )
Độ phức tạp của không gian - O (n)
Ví dụ
public class Arrays{
public List<List<int>> ThreeSum(int[] nums){
List<List<int>> res = new List<List<int>>();
if (nums == null || nums.Length == 0){
return res;
}
var newnums = nums.OrderBy(x => x).ToArray();
for (int i = 0; i < newnums.Count(); i++){
int left = i + 1;
int right = newnums.Count() - 1;
while (left < right){
int sum = newnums[i] + newnums[left] + newnums[right];
if (sum == 0){
List<int> l = new List<int>();
l.Add(newnums[i]);
l.Add(newnums[left]);
l.Add(newnums[right]);
res.Add(l);
int leftValue = newnums[left];
while (left < newnums.Length && leftValue == newnums[left]){
left++;
}
int riightValue = newnums[right];
while (right > left && riightValue == newnums[right]){
right--;
}
}
else if (sum < 0){
left++;
}
else{
right--;
}
}
while (i + 1 < newnums.Length && newnums[i] == newnums[i + 1]){
i++;
}
}
return res;
}
}
static void Main(string[] args){
Arrays s = new Arrays();
int[] nums = { -1, 0, 1, 2, -1, -4 };
var ss = s.ThreeSum(nums);
foreach (var item in ss){
foreach (var item1 in item){
Console.WriteLine(item1);
}
}
} Đầu ra
[[-1,-1,2],[-1,,0,1]]