なぜ？counterintuitive

長さ n の 0 から始まる整数配列 nums と整数ターゲットを指定すると、0 <= i < j < n および nums[i] + nums[j] < target であるペア (i, j) の数を返します。

私は
return sum(nums[i] + nums[j] < t for i in range(len(nums)-1) for j in range(i+1, len(nums)))
のようなnaive な実装をした。
でもソートしてからtwo pointersでやってるひとがおおかった。ソートしたら順番がずれるからインデックスは？？っておもってそんなこと考えなかった。なんでソートしちゃっても良いんですか？？？？？

質問者からの補足コメント

• 

  結局全ペアを見るから
  更にそれは
  足し算が可換だから
  にboils down??

    補足日時：2024/05/30 18:09

No.5 ベストアンサー 回答者： tknakamuri 回答日時： 2024/05/31 12:11

i < j という条件は (i, j) = (2, 3) と (3, 2) というように、同じ要素の組み合わせを重複して取り出すのを防ぐためでしょう。

順列ではなく組み合わせでデータを取り出すときの常とう手段です。

データの順番は関係ありません。

例えば 1~10 が書いてあるカードを100枚用意したとき
かいてある数字の和が 5 未満になるカードの組み合わせ数は
カードの順番を変えても変わりませんよね。変わったら驚愕です。

nums[i] + nums[j] < t　

という条件の性質上、nums がソートされていると j が増えてゆくと
nums[j] も増えてゆきますから、j のループは
nums[i] + nums[j] < t が False になった時に打ち切ることができます。

sort の処理量は O(nlogn)
組み合わせを取り出す処理量は O(n^2)
ですから、n が十分大きければ sort の処理量は無視できるでしょう。
とすると、組み合わせを取り出す処理量 を端折れた方が
有利になりそうです。特に t が小さいときは効果絶大でしょう。

この回答へのお礼

すこいわかりやすかったです。
ありがとうございます uwu

お礼日時：2024/06/01 18:41

No.4 回答者： mtrajcp 回答日時： 2024/05/30 21:21

i<j

nums[i] + nums[j] < target であるペア (i, j) の数
は
i<j
nums[i] + nums[j] < target であるペア (nums[i],nums[j]) の数
と
同じで

i<j
nums[i] + nums[j] < target であるペア (nums[i],nums[j]) の数
は
ソートしても
変わらないから
ソートしてもよい

例えば

target=4
で

nums[i] + nums[j] < target であるペア(nums[i],nums[j])の数は

nums[]={1,2,3}の場合1+2<4だから(1,2)の1つ
nums[]={1,3,2}の場合1+2<4だから(1,2)の1つ
nums[]={2,1,3}の場合2+1<4だから(2,1)の1つ
nums[]={2,3,1}の場合2+1<4だから(2,1)の1つ
nums[]={3,1,2}の場合1+2<4だから(1,2)の1つ
nums[]={3,2,1}の場合2+1<4だから(2,1)の1つ

のように順序を入れ替えてもすべて同じになる

この回答へのお礼

ありがとうございます。やっぱりわたしの最初のであつてましたね☻
つまりターケっと以下のペア任意に選んでインデックスの前後関係こうなってるねっていうだけだから。

お礼日時：2024/05/30 21:43

No.3 回答者： mtrajcp 回答日時： 2024/05/30 20:46

i<j

nums[i] + nums[j] < target であるペア (i, j) の数
は
i<j
nums[i] + nums[j] < target であるペア (nums[i],nums[j]) の数
と
同じだから
ソートしてもよい

例えば

target=4
で

nums[i] + nums[j] < target であるペア(nums[i],nums[j])の数は

nums[]={1,2,3}の場合1+2<4だから(1,2)の1つ
nums[]={1,3,2}の場合1+2<4だから(1,2)の1つ
nums[]={2,1,3}の場合2+1<4だから(2,1)の1つ
nums[]={2,3,1}の場合2+1<4だから(2,1)の1つ
nums[]={3,1,2}の場合1+2<4だから(1,2)の1つ
nums[]={3,2,1}の場合2+1<4だから(2,1)の1つ

この回答へのお礼

ありがとうございますでも、
nums[i] + nums[j] < target であるペア (i, j) の数
は
i<j
nums[i] + nums[j] < target であるペア (nums[i],nums[j]) の数
と
同じだから

は帰結をなにも出してないと思います。

お礼日時：2024/05/30 20:55

No.2 回答者： だいぬ 回答日時： 2024/05/30 18:41

ソートすれば、i ,jのループについてnums[i] + nums[j]>= targetになった時、それ以上ループを回す必要が無い

それ以上にしかなり得ないから

別にどんな方法でも実装出来れば良くって、何がいいかは要件により変わる。

純粋な話1万レコードあるテーブルとかだったら無駄な処理をして処理効率を悪くする必要が無い

この回答へのお礼

そですね。ありがとうございますʕ•̀ω•́ʔ✧ ちなみにこれはleetcodeていうのの問題です。

お礼日時：2024/05/30 20:09

No.1 回答者： だいぬ 回答日時： 2024/05/30 18:23

i,jを返すのではなく条件を満たすi,jのペアの個数を数えるのですね。

それなら、ソートすれば途中でやめても全て捜索したことになるからじゃないですかね。
どんなアルゴリズムがいいかは要件によって変わります。i,jをそのまま知りたいなら、ソートしては行けないかもしれません。

ただ、ソートしてもインデックスがそのままの言語もあります。
そもそも、ソートする前にインデックスと値をペアで別に持っていればいいわけですね。

この回答へのお礼

もうちょと簡単な日本語でおねがいします

お礼日時：2024/05/30 18:27