次のコードの背後にあるロジックを理解しようとしていますが、ロジックをサポートする数学が現時点では完全に明確ではないため、コードの2つの部分について部分的に不明です。
混乱1：配列の合計を見つける前に、なぜカウント= 1で0をマップに入れるのかわかりませんか？それはどのように役立ちますか？
混乱2：map.put(sum, map.getOrDefault(sum)+1) if（）条件の後に移動すると、正しい解が得られます。ただし、以下のコードのような場所に置くと、間違った結果になります。問題は、カウントを見つけるためにマップでsum-kの値を検索するときに、なぜこれの位置が重要なのかということです。
public int subarraySum(int[] nums, int k) {
HashMap<Integer,Integer> prefixSumMap = new HashMap<>();
prefixSumMap.put(0, 1); // CONFUSION 1
int sum = 0;
int count = 0;
for(int i=0; i<nums.length; i++) {
sum += nums[i];
prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0)+1); //CONFUSION 2
if(prefixSumMap.containsKey(sum - k)) {
count += prefixSumMap.get(sum - k);
}
}
return count;
}
これは面白いと思うかもしれません。整数オーバーフローが負の数になるのを防ぐために、longを使用するようにメソッドを変更しました。
これらの方法はどちらも、正の数に対しては問題なく機能します。最初のものははるかに単純ですが、どちらもテスト配列に対して同じカウントを返します。
public static void main(String[] args) {
Random r = new Random();
long[] vals = r.longs(10_000_000, 1, 1000).toArray();
long k = 29329;
System.out.println(positiveValues(vals, k));
System.out.println(anyValues(vals, k));
public static int positiveValues(long[] array, long k) {
Map<Long,Long> map = new HashMap<>(Map.of(0L,1L));
int count = 0;
long sum = 0;
for (long v : array) {
sum += v;
map.put(sum,1L);
if (map.containsKey(sum-k)) {
count++;
}
}
return count;
}
public static int anyValues(long[] nums, long k) {
HashMap<Long,Long> prefixSumMap = new HashMap<>();
prefixSumMap.put(0L, 1L);
long sum = 0;
int count = 0;
for(int i=0; i<nums.length; i++) {
sum += nums[i];
prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0L)+1L);
if(prefixSumMap.containsKey(sum - k)) {
count += prefixSumMap.get(sum - k);
}
}
return count;
}
さらに、ステートメント
long v = prefixSumMap.getOrDefault(sum, 0L) + 1L;
正の配列の場合は常に1を返します。これは、前の合計が正の値のみに対して再遭遇することは決してないためです。
そのステートメント、およびcountマップから値を取得して計算するステートメントは、配列に正の数と負の数の両方を含めることができるようにすることです。そして、これは真実であり-k、すべての正の値です。
次の入力の場合：
long[] vals = {1,2,3,-3,0,3};
合計が3になるサブ配列は次のとおりです。
(1+2), (3), (1+2+3-3), (1+2+3-3+0), (3-3+0+3), (0+3), (3)
負の数を追加すると前の合計になる可能性があるため、それらを考慮する必要があります。正の値のソリューションはこれを行いません。
これは、すべての負の値に対しても機能します。kが正の場合no、すべての合計が負になるため、サブ配列が見つかります。kが負の場合、1つ以上のサブ配列mayが見つかる可能性があります。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加