1995.Count_Special_Quadruplets.md

1995. Count Special Quadruplets

這題是特殊的 3Sum 雖然是 Easy 但是要減少 Time complexity 並不容易。

---

O(n⁴) Solution

最暴力的解法就是直接用 4 個 for loop 來找出所有的 Quadruplets，然後再判斷是否符合條件，這樣的 Time complexity 是 O(n⁴)。

func countQuadruplets(nums []int) int {
    n := len(nums)
    result := 0
    for a := 0; a < n; a++ {
        for b := a+1; b < n; b++ {
            for c := b+1; c < n; c++ {
                for d := c+1; d < n; d++ {
                    if nums[a] + nums[b] + nums[c] == nums[d] {
                        result++
                    }
                }
            }
        }
    }
    return result
}