Cho một số mảng gồm n số nguyên, tìm tất cả các bộ ba a, b, c duy nhất trong mảng sao cho a + b + c = 0
Lưu ý: các bộ 3 không được phép trùng lặp
Lưu ý: các bộ 3 không được phép trùng lặp
Code Editor
Solution:
1. Sort mảng
2. Duyệt từng phần tử với index i trong mảng đã được sort, với mỗi phần tử ta sẽ tính ra được số target (0 - nums[i]). Nếu nums[i] > 0 ta có thể thoát khỏi vòng lặp ngay lập tức vì mảng đã sort nên các số còn lại luôn luôn > 0
3. Dùng 2 pointer với index l (left) và r (right) nếu nums[l] + nums[r] < target tăng index của l, ngược lại nếu lớn hơn thì tăng index của r. Ngay khi tìm đc bộ 3 với nums[l] + nums[r] == target có nghĩa là nums[i] + nums[l] + nums[r] = 0, lưu lại bộ 3 này
4. Để tránh sự trùng lặp các bộ 3 sau khi tìm đc l và r phù hợp ta sẽ tăng l và giảm r cho đến khi tìm được số kế tiếp khác với 2 số left và right được chọn.
1. Sort mảng
2. Duyệt từng phần tử với index i trong mảng đã được sort, với mỗi phần tử ta sẽ tính ra được số target (0 - nums[i]). Nếu nums[i] > 0 ta có thể thoát khỏi vòng lặp ngay lập tức vì mảng đã sort nên các số còn lại luôn luôn > 0
3. Dùng 2 pointer với index l (left) và r (right) nếu nums[l] + nums[r] < target tăng index của l, ngược lại nếu lớn hơn thì tăng index của r. Ngay khi tìm đc bộ 3 với nums[l] + nums[r] == target có nghĩa là nums[i] + nums[l] + nums[r] = 0, lưu lại bộ 3 này
4. Để tránh sự trùng lặp các bộ 3 sau khi tìm đc l và r phù hợp ta sẽ tăng l và giảm r cho đến khi tìm được số kế tiếp khác với 2 số left và right được chọn.
Code Editor