Subarray dengan jumlah yang diberikan di Jawa dengan pendekatan yang berbeza

Mencari subarray dengan jumlah tertentu adalah masalah biasa yang sering muncul dalam temu bual pengekodan dan pengaturcaraan kompetitif. Masalah ini boleh diselesaikan menggunakan pelbagai teknik, masing-masing dengan pertukaran sendiri mengenai kerumitan masa dan kerumitan ruang. Dalam artikel ini, kami akan meneroka pelbagai pendekatan untuk menyelesaikan masalah mencari subarray dengan jumlah tertentu di Jawa.

Pernyataan Masalah

Memandangkan tatasusunan integer dan jumlah sasaran, cari subray berterusan dalam tatasusunan yang menjumlahkan sehingga jumlah yang diberikan. Masalahnya boleh dibahagikan kepada dua varian utama:

1. Subarray dengan Nombor Positif: Tatasusunan mengandungi nombor positif sahaja.
2. Subarray dengan Nombor Bercampur: Tatasusunan mengandungi nombor positif dan negatif.

Jom teroka kaedah berbeza untuk menyelesaikan varian ini.

Pendekatan 1: Menggunakan Brute Force

Pendekatan brute force melibatkan menyemak semua subarray yang mungkin dan mengira jumlah mereka untuk melihat sama ada mana-mana daripadanya menyamai jumlah sasaran. Pendekatan ini berfungsi untuk kedua-dua varian tetapi tidak cekap untuk tatasusunan besar kerana kerumitan masa kuadratiknya.

Pelaksanaan

public class SubarraySumBruteForce {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int n = arr.length;
    for (int start = 0; start < n; start++) {
      int currentSum = 0;
      for (int end = start; end < n; end++) {
        currentSum += arr[end];
        if (currentSum == targetSum) {
          return new int[] {
            start,
            end
          };
        }
      }
    }
    return new int[] {
      -1, -1
    }; // Return -1 if no subarray is found
  }

  public static void main(String[] args) {
    int[] arr = {
      1,
      2,
      3,
      7,
      5
    };
    int targetSum = 12;
    int[] result = findSubarrayWithGivenSum(arr, targetSum);
    if (result[0] != -1) {
      System.out.println("Subarray found from index " + result[0] + " to " + result[1]);
    } else {
      System.out.println("No subarray with given sum found.");
    }
  }
}

Output

Subarray found from index 1 to 3

Analisis

• Kerumitan Masa: O(n²) disebabkan oleh dua gelung bersarang yang berulang melalui tatasusunan.
• Kerumitan Ruang: O(1) kerana tiada ruang tambahan digunakan di luar tatasusunan input.

Pendekatan 2: Menggunakan Tetingkap Gelongsor

Pendekatan tetingkap gelongsor adalah cekap untuk tatasusunan yang mengandungi nombor positif sahaja. Teknik ini melibatkan mengekalkan tetingkap elemen yang menjumlahkan sehingga jumlah sasaran. Tetingkap dikembangkan dengan menambah elemen sehingga jumlah melebihi sasaran, dan mengecut dengan mengalih keluar elemen dari permulaan sehingga jumlah kurang daripada atau sama dengan sasaran.

Pelaksanaan

public class SubarraySumSlidingWindow {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int start = 0;
    int currentSum = 0;

    for (int end = 0; end < arr.length; end++) {
      currentSum += arr[end];

      while (currentSum > targetSum && start < end) {
        currentSum -= arr[start];
        start++;
      }

      if (currentSum == targetSum) {
        return new int[] {
          start,
          end
        };
      }
    }
    return new int[] {
      -1, -1
    }; // Return -1 if no subarray is found
  }

  public static void main(String[] args) {
    int[] arr = {
      1,
      2,
      3,
      7,
      5
    };
    int targetSum = 12;
    int[] result = findSubarrayWithGivenSum(arr, targetSum);
    if (result[0] != -1) {
      System.out.println("Subarray found from index " + result[0] + " to " + result[1]);
    } else {
      System.out.println("No subarray with given sum found.");
    }
  }
}

Output

Subarray found from index 1 to 3

Analisis

• Kerumitan Masa: O(n) kerana setiap elemen diproses paling banyak dua kali.
• Kerumitan Ruang: O(1) kerana tiada ruang tambahan diperlukan.

Atas ialah kandungan terperinci Subarray dengan jumlah yang diberikan di Jawa dengan pendekatan yang berbeza. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!