วิธีง่ายๆ คือ เราสามารถสร้างลูปที่ซ้อนกันสี่วง และตรวจสอบทีละรายการว่าผลรวมขององค์ประกอบทั้งสี่นั้นเป็นศูนย์หรือไม่ หากผลรวมขององค์ประกอบทั้งสี่เป็นศูนย์ ให้พิมพ์องค์ประกอบ
ความซับซ้อนของเวลา − O(n 4 )
ความซับซ้อนของอวกาศ − O(1)
เราสามารถใช้โครงสร้างข้อมูลชุดที่ไม่เรียงลำดับเพื่อเก็บแต่ละค่าของอาร์เรย์ Set ให้ประโยชน์ของการค้นหาองค์ประกอบในเวลา O(1) ดังนั้น สำหรับแต่ละคู่ในอาร์เรย์ เราจะมองหาค่าลบของผลรวมที่อาจมีอยู่ในชุด หากพบองค์ประกอบดังกล่าว เราสามารถพิมพ์แฝดสามซึ่งจะเป็นคู่ของจำนวนเต็มและค่าลบของผลรวมของพวกมัน
ความซับซ้อนของเวลา − O(n 3 )
ความซับซ้อนของอวกาศ − O(n)
ตัวอย่าง
public class Arrays{
public List<List<int>> FourSum(int[] nums){
List<List<int>> res = new List<List<int>>();
if (nums == null || nums.Length == 0){
return null;
}
int[] newNums = nums.OrderBy(x => x).ToArray();
for (int i = 0; i < newNums.Length; i++){
for (int j = i; j < newNums.Length; j++){
int left = j + 1;
int right = newNums.Length - 1;
while (left < right){
int sum = newNums[i] + newNums[j] + newNums[left] + newNums[right];
if (sum == 0){
List<int> sums = new List<int>();
sums.Add(newNums[i]);
sums.Add(newNums[j]);
sums.Add(newNums[left]);
sums.Add(newNums[right]);
res.Add(sums);
int leftValue = newNums[left];
int rightValue = newNums[right];
while (left < nums.Length && leftValue == nums[left]){
left++;
}
while (right > left && right == nums[right]){
right--;
}
}
else if (sum < 0){
left++;
}
else{
right--;
}
}
while (j + 1 < nums.Length && nums[j] == nums[j + 1]){
j++;
}
}
while (i + 1 < nums.Length && nums[i] == nums[i + 1]){
i++;
}
}
return res;
}
}
static void Main(string[] args){
Arrays s = new Arrays();
int[] nums = { 1,0,-1,0,-2,2 };
var ss = FourSum(nums);
foreach (var item in ss){
foreach (var item1 in item){
Console.WriteLine(item1);
}
}
} ผลลัพธ์
[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
