Cùng giải leetcode! Bài 2367. Number of Arithmetic Triplets

Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/number-of-arithmetic-triplets/

1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài

Cho một mảng số nguyên tăng dần nums và một số nguyên diff. Bộ ba (i, j, k) là bộ ba số học nếu thỏa mãn các điều kiện sau:

• i < j < k.
• nums[j] - nums[i] == diff.
• nums[k] - nums[j] == diff.
  Trả về kết quả là số lượng bộ ba số học không trùng lặp có trong mảng nums.

Điều kiện bài toán:

• 3 <= nums.length <= 200.
• 0 <= nums[i] <= 200.
• 1 <= diff <= 50.

Bài toán minh họa 1:

Input: nums = [0,1,4,6,7,10], diff = 3
Output: 2
Explanation:
(1, 2, 4) is an arithmetic triplet because both 7 - 4 == 3 and 4 - 1 == 3.
(2, 4, 5) is an arithmetic triplet because both 10 - 7 == 3 and 7 - 4 == 3.

Bài toán minh họa 2:

Input: nums = [4,5,6,7,8,9], diff = 2
Output: 2
Explanation:
(0, 2, 4) is an arithmetic triplet because both 8 - 6 == 2 and 6 - 4 == 2.
(1, 3, 5) is an arithmetic triplet because both 9 - 7 == 2 and 7 - 5 == 2.

3. Phân tích

Ô kê, bài đọc qua thấy cũng không phức tạp lắm nhỉ? Chúng ta cần làm hai công việc chính để giải quyết bài toán này:

• Tìm ra được bộ ba số học thỏa mãn điều kiện i < j < k, nums[j] - nums[i] == diff và nums[k] - nums[j] == diff.
• Tiếp theo là đếm số lượng bộ ba số học thoa mãn điều kiện trên, nhớ là không được trùng lặp nhé.

Thế là xong! Cũng khá là đơn giản đấy nhể, đến bước tiếp theo thôi!

4. Chạy code bằng cơm

Đầu tiên ta sẽ đặt một biến số nguyên count bằng 0 để đếm số lượng bộ ba số học:

Tiếp theo ta cần có một vòng lặp for để cho i chạy từ đầu đến cuối mảng:

Sau đó để so sánh với số lớn hơn nums[i] ta cần thêm một vòng lặp ở bên trong nó với biến chạy là j = i + 1:

Vậy là j sẽ chạy từ i+1 đến hết mảng:

Và chúng ta cần kiểm tra xem là num[j] - nums[i] == diff hay không:

Khi i = 1 và j = 2, ta thấy thỏa mãn điều kiện trên:

Nếu thỏa mãn điều kiện trên, chúng ta thêm một vòng lặp nữa bên trong với biến k chạy từ j+1 đến hết mảng:

Khi i = 1, j = 2 và k = 4 thì ta thấy thỏa mãn điều kiện cuối cùng là nums[k] - nums[j] == diff:

Thì ta sẽ thêm 1 vào biến count:

Cứ thế đến hết mảng, chúng ta sẽ có kết quả count là số lượng bộ ba số học không bị trùng lặp cần tìm.

5. Code thôi chờ gì nữa

Về cơ bản code của chúng ta sẽ như sau:

 public static int arithmeticTriplets(int[] nums, int diff) {
     int count = 0;

     for (int i = 0; i < nums.length; i++) {
         for (int j = i+1; j < nums.length; j++) {
             if (nums[i] + diff == nums[j]) {
                 for (int k = j+1; k < nums.length; k++) {
                     if (nums[j] + diff == nums[k]) {
                         count++;
                     }
                 }
             }
         }
     }

     return count;
 }

Bài toán đã được giải quyết, nhưng vấn đề như các bạn có thể thấy, code của chúng ta quá tệ. Thậm chí Ryu còn có thể dùng Hadouken vào code của chúng ta nữa kìa

Chúng ta cần cải thiện code hơn nữa, nhưng mà làm thế nào? Ok trước hết cùng mình làm toán một chút nhé, theo điều kiện ta có nums[j] - nums[i] == diff, nên suy ra:

Tiếp theo thay nums[j] = nums[i] + diff vào biểu thức nums[k] - nums[j] == diff, ta có:

Qua đó điều kiện đề bài sẽ rút gọn, tập trung vào nums[i]:

Tiếp theo, vì tính chất không trùng lặp mà đề bài đã yêu cầu, chúng ta có thể sử dụng HashSet để giải quyết bài toán này. Ta sẽ duyệt qua mảng, đặt điều kiện cứ khi nào gặp số nguyên i thỏa mãn điều kiện trên thì count +1. Code của chúng ta sẽ như sau:

 public static int arithmeticTriplets(int[] nums, int diff) {
     int count = 0;
     Set<Integer> mySet = new HashSet<>();

     for (Integer i : nums) {
         if (mySet.contains(i - diff) && mySet.contains(i - diff*2)) {
             count++;
         }
         mySet.add(i);
     }

     return count;
 }

6. Kết thúc

Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!