森田賢二のleetCodeの使い方、解説、解答を毎日更新しているキャラクター
もりたけんじ

leetCode分かる日記(2) 3sum

leetCode分かる日記(2)

3sum

https://leetcode.com/problems/3sum/

leetCode

3sum

早くも答え見なくては解けなくなった

n個の要素がある配列の中で、3つを使って合計0になるような組み合わせをあるだけ
num[][]型で作れというもの

どうやって、3つをあてていくのだろうと考えていたが
自分の今持っている引き出しではできなかった

リンク先はJavaだが
https://www.programcreek.com/2012/12/leetcode-3sum/

JSにするとこういうことになる

var threeSum = function(nums) {
  nums.sort();
  console.log(nums);
  var result = [];
  for(let i = 0; i < nums.length; i++){
    let j = i + 1;
    let k = nums.length -1;
    if(i > 0 && nums[i] === nums[i - 1]){
      continue;
    }
    while(j < k){
      if(k < nums.length - 1 && nums[k] === nums[k + 1]){
        k--;
        continue;
      }
      if(nums[i] + nums[j] + nums[k] > 0){
        k--;
      } else if(nums[i] + nums[j] + nums[k] < 0){
        j++;
      } else {
        let l = [];
        l.push(nums[i]);
        l.push(nums[j]);
        l.push(nums[k]);
        result.push(l);
        j++;
        k--;
      }
    }
  }
  return result;
}
var nums = [-1, 0, 1, 2, -1, -4]
const v = threeSum(nums)
console.log(v)

理解を置いて行った記述になった...

配列の要素の最後の値(k)と
配列の要素最初(i)と最初の次(j)を

jがkを超えないうちはwhileで回す

if(k < nums.length - 1 && nums[k] === nums[k + 1]){
   k--;
   continue;
}

kがnumsのインデックスより少なく、kの位置にあるnumsの要素がkの次にあるnumsの要素と同じなら
kを一つ減らす...

[-1, 0, 1, 2, -1, -4]とあったら、
kはnums.length -1で5
5 < 5はfalseなので
ここは通らない...

      if(nums[i] + nums[j] + nums[k] > 0){
        k--;
      } else if(nums[i] + nums[j] + nums[k] < 0){
        j++;
      } else { ....

ここは、

nums[i] + nums[j] + nums[k] > 0)

-1 + 0 + -4 > 0 がfalseなので通らず、

次の

nums[i] + nums[j] + nums[k] < 0)

は
-1 + 0 + -4 < 0
はtrue
なので
jが一つ加算される

で、次のループ
つまり0にならない

0より少ない場合jを一つ足して
0より多い場合kを一つ減らす

あー...
最初sortして整えていたのはそのためか...

つまり...

kがjより大きいうちは回すは

jがkを超えることは同じ重複した値にアクセスすることになるからで
同時に
配列の要素0から始まるiとjが最後の-1から始まるkと挟み込む様に出会うまで
計算していき...

効率の良いアクセスの仕方と理解したが

その後は....

つづく...

「武骨日記の」プライバシーポリシーに関して
・プライバシーポリシー
・個人情報取り扱いに関して

・サイトTOP
・私は何者か
・29歳よしもと芸人がWebデザイナー未経験で学校に通い5年後フリーランスのフロントエンドエンジニアになるためにやった9つのこと
・フロント記事
・フロントエンドエンジニア
・フロントエンド記事(タグ)
・TypeScript
・TypeScript練習問題集
・【TypeScript】TypeSript中級者になる為に知っておくと良い108個のこと
・JavaScript練習問題
・styled-componentsの使い方
・SCSS問題集
・GraphQL「Apollo x Relay-Style-Cursor-Pagination(リレースタイルカーソルページネーション)」
・recomposeと仲良くなりたい
・機動戦士FlowType
・初めてReactNativeWebを触ってみて
・Ramda.jsシグネチャの読み方
・環境変数の話
・いちごタルトの作り方
・フロントエンドエンジニア豚汁の作り方

「武骨日記の」プライバシーポリシーに関して
プライバシーポリシー

株式会社TerraceTechについて
最近起業しました。
・株式会社TerraceTech

SNS
・しずかなインターネット kenjimorita
・インド旅　instagram
・適当な日常写真　instagram
・シュールさーん　instagram
・シュールさーん LINEスタンプ
・もりたけんじTwitter
・ネタ帳Twitter
・note

・FaceBook -kennji.morita-

※わたしが結成しているWebチームではWeb未経験者、フリーランスの方へのお仕事を紹介しています。
また個人レッスンしてほしい生徒も募集中です。
もしご興味ある方はチャットからご連絡ください。

※業務連絡やお久しぶり連絡もチャットからお願いします。