leetcode 18 - 4sum | Optimal Approach in JAVA . скачать в хорошем качестве

leetcode 18 - 4sum | Optimal Approach in JAVA .

#18leetcode #java #education Input nums = [2, 2, 2, 2, 2], target = 8 Step 1: Sort the array Sorted nums = [2, 2, 2, 2, 2] (already sorted). Step 2: Choose first number (i) Pick i = 0 → value = 2. This is the first element of the quadruplet. Step 3: Choose second number (j) Pick j = 1 → value = 2. This is the second element of the quadruplet. Step 4: Two-pointer search for the last two numbers Left pointer k = 2 → value = 2 Right pointer l = 4 → value = 2 Now we have: quadruplet = [2, 2, 2, 2] sum = 2 + 2 + 2 + 2 = 8 Step 5: Compare with target The sum equals the target (8). So, store this quadruplet: Result = [[2, 2, 2, 2]] Step 6: Move pointers and skip duplicates Move k forward, move l backward. Now k meets l, so stop this inner search. Any further choices of j or i would repeat the same value (2), so they are skipped as duplicates. Final Answer [[2, 2, 2, 2]] ✅ From the problem’s perspective: The algorithm finds only one unique quadruplet, even though many 2’s exist in the array, because duplicates are skipped. Problem: Given an array of integers nums and an integer target, find all unique quadruplets [a, b, c, d] in the array such that: a + b + c + d = target Key Challenges: Avoid duplicate quadruplets. Handle both positive and negative numbers. Prevent integer overflow (sum of four numbers can exceed int range). Improve efficiency beyond brute force (O(n⁴)). 🔹 Algorithm (Structured Steps) Step 1: Sort the array Sorting helps in two ways: It allows us to apply the two-pointer technique. It makes duplicate removal easy (skip repeated numbers). Step 2: Fix the first element (i) Iterate from start to end. For each index i, treat nums[i] as the first element of the quadruplet. Skip duplicates: if nums[i] == nums[i-1], continue. Step 3: Fix the second element (j) For each i, run another loop starting from i+1. Treat nums[j] as the second element. Again, skip duplicates: if nums[j] == nums[j-1], continue. Step 4: Use two pointers for remaining elements (k and l) Initialize: k = j+1 (just after j) l = n-1 (end of array) While k (less than ) l, calculate the sum: sum = nums[i] + nums[j] + nums[k] + nums[l] Step 5: Compare sum with target Case 1: sum == target Found a valid quadruplet → add [nums[i], nums[j], nums[k], nums[l]] to result. Move both pointers (k++, l--). Skip duplicates for both k and l. Case 2: sum less than target Increase the sum → move k++. Case 3: sum greater than target Decrease the sum → move l--. Step 6: Continue search Repeat until all possibilities for i, j, k, l are checked. Ensure uniqueness by skipping duplicates at every stage. Step 7: Return result Return the list of all unique quadruplets that satisfy the condition. 🔹 Complexity Time Complexity: O(n³) Outer loop (i) → O(n) Inner loop (j) → O(n) Two-pointer loop (k, l) → O(n) Total = O(n³) Space Complexity: O(1) extra (only storing results). 🔹 Summary Problem solved using: Sorting + Two-pointer technique. Approach: Reduce 4-Sum to 2-Sum by fixing two numbers and searching for the remaining pair. Key Idea: Sorting + duplicate skipping ensures correctness and uniqueness.