객체를 사용하면 키가 지정된 값 컬렉션을 저장할 수 있습니다. 괜찮습니다.
그러나 우리는 첫 번째, 두 번째, 세 번째 요소 등을 포함하는 순서가 지정된 컬렉션이 필요하다는 것을 자주 발견합니다. 예를 들어 사용자, 상품, HTML 요소 등의 목록을 저장하려면 해당 정보가 필요합니다.
여기서는 개체의 순서를 관리하는 메서드를 제공하지 않기 때문에 개체를 사용하는 것이 편리하지 않습니다. 기존 속성 "사이"에 새 속성을 삽입할 수는 없습니다. 객체는 그러한 용도로 사용되지 않습니다.
정렬된 컬렉션을 저장하기 위해 Array 라는 특수 데이터 구조가 있습니다.
빈 배열을 만드는 데는 두 가지 구문이 있습니다.
let arr = new Array(); arr = [];
거의 항상 두 번째 구문이 사용됩니다. 괄호 안에 초기 요소를 제공할 수 있습니다.
let 과일 = ["사과", "오렌지", "자두"];
배열 요소에는 0부터 시작하여 번호가 매겨집니다.
대괄호 안의 숫자로 요소를 얻을 수 있습니다.
let 과일 = ["사과", "오렌지", "자두"]; 경고( 과일[0] ); // 사과 경고(과일[1]); // 주황색 경고(과일[2]); // 자두
요소를 교체할 수 있습니다:
과일[2] = '배'; // 이제 ["사과", "오렌지", "배"]
…또는 배열에 새 항목을 추가합니다.
과일[3] = '레몬'; // 이제 ["사과", "오렌지", "배", "레몬"]
배열에 있는 요소의 총 개수는 length 입니다.
let 과일 = ["사과", "오렌지", "자두"]; 경고(과일.길이); // 3
전체 배열을 표시하기 위해 alert 사용할 수도 있습니다.
let 과일 = ["사과", "오렌지", "자두"]; 경고(과일); // 사과, 오렌지, 자두
배열은 모든 유형의 요소를 저장할 수 있습니다.
예를 들어:
// 값 혼합
let arr = [ 'Apple', { name: 'John' }, true, function() { Alert('hello'); } ];
// 인덱스 1의 객체를 가져온 다음 이름을 표시합니다.
경고( arr[1].name ); // 존
// 인덱스 3에서 함수를 가져와서 실행합니다.
arr[3](); // 안녕하세요후행 쉼표
배열은 객체와 마찬가지로 쉼표로 끝날 수 있습니다.
과일 = [ "사과", "주황색", "자두", ];
"후행 쉼표" 스타일을 사용하면 모든 줄이 비슷해지기 때문에 항목을 삽입/제거하기가 더 쉽습니다.
최근 추가된 내용
이것은 최근에 언어에 추가된 것입니다. 오래된 브라우저에는 폴리필이 필요할 수 있습니다.
배열의 마지막 요소를 원한다고 가정해 보겠습니다.
일부 프로그래밍 언어에서는 fruits[-1] 과 같이 동일한 목적으로 음수 인덱스 사용을 허용합니다.
하지만 JavaScript에서는 작동하지 않습니다. 대괄호 안의 인덱스는 문자 그대로 처리되므로 결과는 undefined 됩니다.
마지막 요소 인덱스를 명시적으로 계산한 다음 이를 액세스할 수 있습니다: fruits[fruits.length - 1] .
let 과일 = ["사과", "오렌지", "자두"]; 경고(과일[과일.길이-1]); // 자두
좀 번거롭지 않나요? 변수 이름을 두 번 작성해야 합니다.
운 좋게도 더 짧은 구문이 있습니다: fruits.at(-1) :
let 과일 = ["사과", "오렌지", "자두"]; // 과일[과일.길이-1]과 동일 경고(fruits.at(-1) ); // 자두
즉, arr.at(i) :
i >= 0 인 경우 arr[i] 와 정확히 동일합니다.
i 의 음수 값의 경우 배열 끝에서 뒤로 물러납니다.
큐는 배열의 가장 일반적인 용도 중 하나입니다. 컴퓨터 과학에서 이는 두 가지 작업을 지원하는 순서가 지정된 요소 모음을 의미합니다.
push 끝에 요소를 추가합니다.
shift 처음부터 요소를 가져와 대기열을 진행시켜 두 번째 요소가 첫 번째 요소가 되도록 합니다.
배열은 두 작업을 모두 지원합니다.
실제로는 매우 자주 필요합니다. 예를 들어 화면에 표시되어야 하는 메시지 대기열이 있습니다.
배열의 또 다른 사용 사례가 있습니다. 바로 스택이라는 데이터 구조입니다.
이는 두 가지 작업을 지원합니다.
push 끝에 요소를 추가합니다.
pop 끝에서 요소를 가져옵니다.
따라서 항상 "끝"부터 새로운 요소가 추가되거나 제거됩니다.
스택은 일반적으로 카드 팩으로 설명됩니다. 새 카드는 맨 위에 추가되거나 맨 위에서 가져옵니다.
스택의 경우 가장 최근에 푸시된 항목이 먼저 수신되는데, 이를 LIFO(Last-In-First-Out) 원칙이라고도 합니다. 대기열에는 FIFO(선입선출)가 있습니다.
JavaScript의 배열은 대기열과 스택으로 모두 작동할 수 있습니다. 시작 또는 끝에서 요소를 추가/제거할 수 있습니다.
컴퓨터 과학에서는 이를 가능하게 하는 데이터 구조를 데크(deque)라고 합니다.
배열의 끝에서 작동하는 메서드:
pop
배열의 마지막 요소를 추출하여 반환합니다.
let 과일 = ["사과", "오렌지", "배"]; 경고(과일.팝()); // "Pear"를 제거하고 경고합니다. 경고(과일); // 사과, 오렌지
fruits.pop() 과 fruits.at(-1) 은 모두 배열의 마지막 요소를 반환하지만, fruits.pop() 도 배열을 제거하여 수정합니다.
push
배열 끝에 요소를 추가합니다.
let 과일 = ["사과", "오렌지"];
Fruits.push("배");
경고(과일); // 사과, 오렌지, 배 fruits.push(...) 호출은 fruits[fruits.length] = ... 와 같습니다.
배열의 시작 부분에서 작동하는 메서드:
shift
배열의 첫 번째 요소를 추출하여 반환합니다.
let 과일 = ["사과", "오렌지", "배"]; 경고(fruits.shift()); // Apple을 제거하고 경고합니다. 경고(과일); // 오렌지, 배
unshift
배열의 시작 부분에 요소를 추가합니다.
let 과일 = ["오렌지", "배"];
과일.unshift('사과');
경고(과일); // 사과, 오렌지, 배 push 및 unshift 메소드는 한 번에 여러 요소를 추가할 수 있습니다.
과일 = ["사과"];
과일.push("오렌지", "복숭아");
과일.unshift("파인애플", "레몬");
// ["파인애플", "레몬", "사과", "오렌지", "복숭아"]
경고(과일); 배열은 특별한 종류의 객체입니다. arr[0] 속성에 액세스하는 데 사용되는 대괄호는 실제로 개체 구문에서 나옵니다. 이는 본질적으로 obj[key] 와 동일합니다. 여기서 arr 은 객체이고 숫자는 키로 사용됩니다.
순서가 지정된 데이터 컬렉션과 length 속성을 사용하기 위한 특별한 방법을 제공하는 개체를 확장합니다. 그러나 핵심은 여전히 객체입니다.
JavaScript에는 8가지 기본 데이터 유형만 있다는 것을 기억하세요(자세한 내용은 데이터 유형 장을 참조하세요). 배열은 객체이므로 객체처럼 동작합니다.
예를 들어, 참조로 복사됩니다.
과일 = ["바나나"]
arr = 과일이라고 하자; // 참조로 복사(두 변수가 동일한 배열을 참조)
경고( arr === 과일 ); // 진실
arr.push("배"); // 참조로 배열을 수정합니다.
경고(과일); // 바나나, 배 - 이제 항목 2개…그러나 배열을 정말 특별하게 만드는 것은 내부 표현입니다. 엔진은 이 장의 그림에 설명된 것처럼 인접한 메모리 영역에 해당 요소를 하나씩 저장하려고 시도하며 배열이 정말 빠르게 작동하도록 하기 위한 다른 최적화도 있습니다.
그러나 "순서가 지정된 컬렉션"처럼 배열 작업을 중단하고 마치 일반 개체인 것처럼 작업을 시작하면 모두 깨집니다.
예를 들어 기술적으로 다음과 같이 할 수 있습니다.
과일 = []; // 배열을 만든다 과일[99999] = 5; // 길이보다 훨씬 큰 인덱스를 가진 속성을 할당합니다. 과일.나이 = 25; // 임의의 이름을 가진 속성을 생성합니다.
배열은 기본 객체이기 때문에 가능합니다. 여기에 어떤 속성이라도 추가할 수 있습니다.
그러나 엔진은 우리가 일반 개체와 마찬가지로 배열을 사용하여 작업하고 있음을 알 수 있습니다. 이러한 경우에는 어레이별 최적화가 적합하지 않으며 꺼지고 해당 이점도 사라집니다.
배열을 오용하는 방법:
arr.test = 5 와 같이 숫자가 아닌 속성을 추가하세요.
다음과 같이 구멍을 만드세요. arr[0] 추가한 다음 arr[1000] 추가하세요(그 사이에는 아무 것도 없습니다).
arr[1000] , arr[999] 등과 같이 역순으로 배열을 채웁니다.
배열을 정렬된 데이터 로 작업하기 위한 특수 구조로 생각하십시오. 이를 위해 특별한 방법을 제공합니다. 배열은 연속적으로 정렬된 데이터와 작동하도록 JavaScript 엔진 내에서 신중하게 조정됩니다. 이 방법으로 사용하십시오. 그리고 임의의 키가 필요한 경우 실제로 일반 객체 {} 가 필요할 가능성이 높습니다.
push/pop 메소드는 빠르게 실행되는 반면 shift/unshift 는 느립니다.
배열의 시작 부분보다 끝 부분을 작업하는 것이 더 빠른 이유는 무엇입니까? 실행 중에 어떤 일이 발생하는지 살펴보겠습니다.
과일.shift(); // 처음부터 1개의 요소를 가져옵니다.
인덱스가 0 인 요소를 취하고 제거하는 것만으로는 충분하지 않습니다. 다른 요소의 번호도 다시 매겨야 합니다.
shift 작업은 다음 3가지 작업을 수행해야 합니다.
인덱스가 0 인 요소를 제거합니다.
모든 요소를 왼쪽으로 이동하고 인덱스 1 에서 0 , 2 에서 1 등으로 번호를 다시 매깁니다.
length 속성을 업데이트합니다.
배열에 요소가 많을수록 이동하는 데 더 많은 시간이 걸리고 메모리 내 작업도 더 많이 수행됩니다.
unshift 에서도 비슷한 일이 발생합니다. 배열의 시작 부분에 요소를 추가하려면 먼저 기존 요소를 오른쪽으로 이동하여 해당 인덱스를 늘려야 합니다.
push/pop 은 무엇인가요? 아무것도 움직일 필요가 없습니다. 끝에서 요소를 추출하기 위해 pop 메소드는 인덱스를 정리하고 length 줄입니다.
pop 작업에 대한 작업:
과일.팝(); // 끝에서 1개의 요소를 가져옵니다.
pop 메소드는 다른 요소가 색인을 유지하므로 아무것도 이동할 필요가 없습니다. 그렇기 때문에 엄청나게 빠릅니다.
push 방법도 비슷합니다.
배열 항목을 순환하는 가장 오래된 방법 중 하나는 인덱스에 대한 for 루프입니다.
let arr = ["사과", "오렌지", "배"];
for (let i = 0; i < arr.length; i++) {
경고( arr[i] );
} 그러나 배열의 경우 for..of 또 다른 형태의 루프가 있습니다.
let 과일 = ["사과", "오렌지", "자두"];
// 배열 요소를 반복합니다.
for (과일의 과일을 보자) {
경고(과일);
} for..of 는 현재 요소의 수에 대한 액세스를 제공하지 않고 해당 값만 제공하지만 대부분의 경우 충분합니다. 그리고 더 짧습니다.
기술적으로 배열은 객체이기 때문에 for..in 사용할 수도 있습니다.
let arr = ["사과", "오렌지", "배"];
for (arr에 키를 넣음) {
경고( arr[키] ); // 사과, 오렌지, 배
}그러나 그것은 실제로 나쁜 생각이다. 여기에는 잠재적인 문제가 있습니다.
for..in 루프는 숫자 속성뿐만 아니라 모든 속성을 반복합니다.
브라우저와 다른 환경에는 배열처럼 보이는 소위 "배열 같은" 개체가 있습니다. 즉, length 및 indexes 속성이 있지만 일반적으로 필요하지 않은 숫자가 아닌 다른 속성과 메서드도 있을 수 있습니다. for..in 루프는 그것들을 나열합니다. 따라서 배열과 유사한 객체로 작업해야 하는 경우 이러한 "추가" 속성이 문제가 될 수 있습니다.
for..in 루프는 배열이 아닌 일반 객체에 최적화되어 있으므로 10~100배 느립니다. 물론 지금도 매우 빠르다. 속도 향상은 병목 현상이 있는 경우에만 중요할 수 있습니다. 그러나 여전히 우리는 차이점을 인식해야 합니다.
일반적으로 배열에는 for..in 사용하면 안 됩니다.
배열을 수정하면 length 속성이 자동으로 업데이트됩니다. 정확하게 말하면 배열의 값 개수가 아니라 가장 큰 숫자 인덱스에 1을 더한 값입니다.
예를 들어, 큰 인덱스를 가진 단일 요소는 큰 길이를 제공합니다.
과일 = []; 과일[123] = "사과"; 경고(과일.길이); // 124
우리는 일반적으로 그런 배열을 사용하지 않습니다.
length 속성의 또 다른 흥미로운 점은 쓰기 가능하다는 것입니다.
수동으로 늘리면 흥미로운 일이 발생하지 않습니다. 그러나 이를 줄이면 배열이 잘립니다. 이 프로세스는 되돌릴 수 없습니다. 예는 다음과 같습니다.
arr = [1, 2, 3, 4, 5]로 설정합니다. 배열 길이 = 2; // 2개 요소로 자름 경고(arr); // [1, 2] 배열 길이 = 5; // 길이를 다시 반환 경고( arr[3] ); // 정의되지 않음: 값이 반환되지 않습니다.
따라서 배열을 지우는 가장 간단한 방법은 다음과 같습니다. arr.length = 0; .
배열을 생성하는 구문이 하나 더 있습니다:
let arr = new Array("사과", "배", "etc"); 대괄호 [] 가 더 짧기 때문에 거의 사용되지 않습니다. 게다가 까다로운 기능도 있습니다.
숫자인 단일 인수를 사용하여 new Array 호출하면 항목은 없지만 주어진 길이를 갖는 배열이 생성됩니다.
발에 총을 쏠 수 있는 방법을 살펴보겠습니다.
arr = new Array(2); // [2]의 배열을 생성할까요? 경고( arr[0] ); // 한정되지 않은! 요소가 없습니다. 경고(arr.length); // 길이 2
그러한 놀라움을 피하기 위해 우리는 실제로 무엇을 하고 있는지 알지 않는 한 일반적으로 대괄호를 사용합니다.
배열에는 배열이기도 한 항목이 있을 수 있습니다. 예를 들어 행렬을 저장하기 위해 다차원 배열에 사용할 수 있습니다.
행렬 = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]; 경고(행렬[0][1] ); // 2, 첫 번째 내부 배열의 두 번째 값
배열에는 쉼표로 구분된 요소 목록을 반환하는 자체 toString 메서드 구현이 있습니다.
예를 들어:
arr = [1, 2, 3]으로 설정합니다. 경고(arr); // 1,2,3 경고( String(arr) === '1,2,3' ); // 진실
또한 다음을 시도해 봅시다:
경고( [] + 1 ); // "1" 경고( [1] + 1 ); // "11" 경고( [1,2] + 1 ); // "1,21"
배열에는 Symbol.toPrimitive 도 없고 실행 가능한 valueOf 도 없으며 toString 변환만 구현하므로 여기서 [] 는 빈 문자열이 되고 [1] 은 "1" 이 되고 [1,2] 는 "1,2" 가 됩니다.
이진 더하기 "+" 연산자가 문자열에 무언가를 추가하면 문자열로도 변환되므로 다음 단계는 다음과 같습니다.
경고( "" + 1 ); // "1" 경고( "1" + 1 ); // "11" 경고( "1,2" + 1 ); // "1,21"
다른 프로그래밍 언어와 달리 JavaScript의 배열은 == 연산자와 비교하면 안 됩니다.
이 연산자는 배열에 대해 특별한 처리가 없으며 다른 객체와 마찬가지로 작동합니다.
규칙을 기억해 봅시다:
두 개체는 동일한 개체에 대한 참조인 경우에만 == 합니다.
== 의 인수 중 하나가 객체이고 다른 하나가 기본 요소인 경우 객체를 기본 요소로 변환 장에 설명된 대로 개체가 기본 요소로 변환됩니다.
… null 과 undefined 은 서로 == 이고 다른 것은 제외됩니다.
엄격한 비교 === 유형을 변환하지 않으므로 훨씬 더 간단합니다.
따라서 배열을 == 와 비교하면 정확히 동일한 배열을 참조하는 두 변수를 비교하지 않는 한 결코 동일하지 않습니다.
예를 들어:
경고( [] == [] ); // 거짓 경고( [0] == [0] ); // 거짓
이러한 배열은 기술적으로 다른 개체입니다. 그래서 그들은 동등하지 않습니다. == 연산자는 항목별 비교를 수행하지 않습니다.
기본 요소와 비교하면 겉보기에 이상한 결과가 나타날 수도 있습니다.
경고( 0 == [] ); // 진실
경보('0' == [] ); // 거짓 여기서는 두 경우 모두 기본 요소를 배열 개체와 비교합니다. 따라서 [] 배열은 비교를 위해 기본 형식으로 변환되고 빈 문자열 '' 이 됩니다.
그런 다음 유형 변환 장에 설명된 대로 기본 요소를 사용하여 비교 프로세스가 진행됩니다.
// []가 ''로 변환된 후
경고( 0 == '' ); // true, ''가 숫자 0으로 변환되므로
경보('0' == '' ); // false, 유형 변환 없음, 다른 문자열그렇다면 배열을 비교하는 방법은 무엇입니까?
간단합니다. == 연산자를 사용하지 마세요. 대신 루프에서 항목별로 비교하거나 다음 장에 설명된 반복 방법을 사용하십시오.
배열은 정렬된 데이터 항목을 저장하고 관리하는 데 적합한 특별한 종류의 객체입니다.
선언:
// 대괄호(보통) let arr = [항목1, 항목2...]; // 새로운 배열 (예외적으로 드물다) let arr = new Array(item1, item2...);
new Array(number) 를 호출하면 지정된 길이의 배열이 생성되지만 요소는 포함되지 않습니다.
length 속성은 배열 길이 또는 정확하게 말하면 마지막 숫자 인덱스에 1을 더한 값입니다. 배열 방법으로 자동 조정됩니다.
length 수동으로 줄이면 배열이 잘립니다.
요소 가져오기:
arr[0] 처럼 인덱스로 요소를 얻을 수 있습니다.
또한 음수 인덱스를 허용하는 at(i) 메서드를 사용할 수도 있습니다. i 의 음수 값의 경우 배열 끝에서 뒤로 이동합니다. i >= 0 이면 arr[i] 와 동일하게 작동합니다.
다음 작업을 통해 배열을 deque로 사용할 수 있습니다.
push(...items) 끝에 items 추가합니다.
pop() 은 끝에서 요소를 제거하고 반환합니다.
shift() 처음부터 요소를 제거하고 반환합니다.
unshift(...items) items 시작 부분에 추가합니다.
배열의 요소를 반복하려면 다음을 수행하십시오.
for (let i=0; i<arr.length; i++) – 가장 빠르게 작동하며 기존 브라우저와 호환됩니다.
for (let item of arr) – 항목에 대한 최신 구문,
for (let i in arr) – 절대 사용하지 마세요.
배열을 비교하려면 == 연산자( > , < 등)를 사용하지 마세요. 배열에 대해 특별한 처리가 없기 때문입니다. 그들은 그것들을 어떤 객체처럼 다루며 그것은 우리가 일반적으로 원하는 것이 아닙니다.
대신 for..of 루프를 사용하여 배열을 항목별로 비교할 수 있습니다.
우리는 계속해서 배열을 사용하고 다음 장 배열 방법에서 요소를 추가, 제거, 추출하고 배열을 정렬하는 더 많은 방법을 연구할 것입니다.
중요도: 3
이 코드는 무엇을 보여줄까요?
let 과일 = ["사과", "배", "오렌지"];
// "복사본"에 새 값을 삽입합니다.
shoppingCart = 과일이라고 놔두세요.
shoppingCart.push("바나나");
// 과일에는 무엇이 들어있나요?
경고(과일.길이); // ?
결과는 4 입니다.
let 과일 = ["사과", "배", "오렌지"];
shoppingCart = 과일이라고 놔두세요.
shoppingCart.push("바나나");
경고(과일.길이); // 4 배열은 객체이기 때문입니다. 따라서 shoppingCart 와 fruits 모두 동일한 배열에 대한 참조입니다.
중요도: 5
5가지 배열 연산을 시도해 보겠습니다.
"Jazz" 및 "Blues" 항목으로 배열 styles 만듭니다.
끝에 "Rock-n-Roll"을 추가합니다.
중간의 값을 "Classics"로 바꿉니다. 중간 값을 찾는 코드는 길이가 홀수인 배열에 대해 작동해야 합니다.
배열의 첫 번째 값을 제거하고 표시합니다.
Rap 과 Reggae 배열 앞에 추가합니다.
프로세스의 배열:
재즈, 블루스 재즈, 블루스, 로큰롤 재즈, 클래식, 로큰롤 클래식, 락앤롤 랩, 레게, 클래식, 로큰롤
let styles = ["재즈", "블루스"];
styles.push("로큰롤");
스타일[Math.floor((styles.length - 1) / 2)] = "고전";
경고(styles.shift());
styles.unshift("랩", "레게");중요도: 5
결과는 무엇입니까? 왜?
arr = ["a", "b"];
arr.push(함수() {
경고( 이 );
});
arr[2](); // ?
arr[2]() 호출은 구문론적으로 오래된 obj[method]() 입니다. obj 역할에는 arr 있고, method 역할에는 2 있습니다.
따라서 객체 메서드로 arr[2] 함수를 호출합니다. 당연히 객체 arr 참조하여 this 수신하고 배열을 출력합니다.
arr = ["a", "b"];
arr.push(함수() {
경고( 이 );
})
arr[2](); // a,b,함수(){...}배열에는 3개의 값이 있습니다. 처음에는 2개와 함수가 있었습니다.
중요도: 4
다음과 같은 sumInput() 함수를 작성하세요.
prompt 사용하여 사용자에게 값을 요청하고 값을 배열에 저장합니다.
사용자가 숫자가 아닌 값, 빈 문자열을 입력하거나 “취소”를 누르면 확인을 완료합니다.
배열 항목의 합계를 계산하고 반환합니다.
PS 0 0 은 유효한 숫자입니다. 0에서 입력을 중단하지 마십시오.
데모 실행
솔루션의 미묘하지만 중요한 세부 사항을 참고하세요. value = +value 이후에는 빈 문자열(정지 기호)과 0(유효한 숫자)을 구분할 수 없기 때문에 prompt 직후에 value 숫자로 변환하지 않습니다. 대신 나중에 하자.
함수 sumInput() {
숫자 = [];
동안 (참) {
let value = 프롬프트("숫자를 입력해주세요.", 0);
// 취소할까요?
if (값 === "" || 값 === null || !isFinite(값)) break;
숫자.푸시(+값);
}
합계 = 0으로 둡니다.
for (숫자 수) {
합계 += 숫자;
}
반환 금액;
}
경고(sumInput());중요도: 2
입력은 숫자 배열입니다(예: arr = [1, -2, 3, 4, -9, 6] .
작업은 항목의 최대 합을 포함하는 arr 의 연속 하위 배열을 찾는 것입니다.
해당 합계를 반환하는 함수 getMaxSubSum(arr) 을 작성하세요.
예를 들어:
getMaxSubSum([-1, 2, 3, -9]) == 5 (강조 표시된 항목의 합계) getMaxSubSum([2, -1, 2, 3, -9]) == 6 getMaxSubSum([-1, 2, 3, -9, 11]) == 11 getMaxSubSum([-2, -1, 1, 2]) == 3 getMaxSubSum([100, -9, 2, -3, 5]) == 100 getMaxSubSum([1, 2, 3]) == 6 (모두 가져옴)
모든 항목이 음수이면 아무 항목도 사용하지 않고(하위 배열이 비어 있음) 합계가 0이라는 의미입니다.
getMaxSubSum([-1, -2, -3]) = 0
가능한 경우 O(n 2 ) 또는 심지어 O(n)과 같은 빠른 솔루션을 생각해 보십시오.
테스트를 통해 샌드박스를 엽니다.
가능한 모든 부분합을 계산할 수 있습니다.
가장 간단한 방법은 모든 요소를 가져와서 그 요소부터 시작하는 모든 하위 배열의 합을 계산하는 것입니다.
예를 들어 [-1, 2, 3, -9, 11] 의 경우:
// -1부터 시작: -1 -1 + 2 -1 + 2 + 3 -1 + 2 + 3 + (-9) -1 + 2 + 3 + (-9) + 11 // 2부터 시작: 2 2 + 3 2 + 3 + (-9) 2 + 3 + (-9) + 11 // 3부터 시작: 3 3 + (-9) 3 + (-9) + 11 // -9부터 시작 -9 -9 + 11 // 11시부터 시작 11
코드는 실제로 중첩 루프입니다. 배열 요소에 대한 외부 루프와 현재 요소부터 시작하는 내부 계산 부분합입니다.
함수 getMaxSubSum(arr) {
maxSum = 0으로 놔두세요; // 요소를 사용하지 않으면 0이 반환됩니다.
for (let i = 0; i < arr.length; i++) {
sumFixedStart = 0으로 놔두세요;
for (let j = i; j < arr.length; j++) {
sumFixedStart += arr[j];
maxSum = Math.max(maxSum, sumFixedStart);
}
}
최대값 반환;
}
경고( getMaxSubSum([-1, 2, 3, -9]) ); // 5
경고( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
경고( getMaxSubSum([-2, -1, 1, 2]) ); // 3
경고( getMaxSubSum([1, 2, 3]) ); // 6
경고( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100이 솔루션의 시간 복잡도는 O(n 2 )입니다. 즉, 배열 크기를 2배로 늘리면 알고리즘 작동 시간은 4배 더 길어집니다.
대규모 배열(1000개, 10000개 이상의 항목)의 경우 이러한 알고리즘은 심각한 속도 저하를 초래할 수 있습니다.
배열을 탐색하고 변수 s 에 있는 요소의 현재 부분합을 유지해 보겠습니다. s 어느 시점에서 음수가 되면 s=0 할당합니다. 그러한 모든 s 최대값이 답이 될 것입니다.
설명이 너무 모호한 경우 코드를 참조하세요. 코드는 매우 짧습니다.
함수 getMaxSubSum(arr) {
maxSum = 0으로 놔두세요;
부분합 = 0으로 놔두세요;
for (let item of arr) { // arr의 각 항목에 대해
부분합 += 항목; //partialSum에 추가
maxSum = Math.max(maxSum, 부분합); // 최대값을 기억하세요
if (partialSum < 0) 부분합 = 0; // 음수이면 0
}
최대값 반환;
}
경고( getMaxSubSum([-1, 2, 3, -9]) ); // 5
경고( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
경고( getMaxSubSum([-2, -1, 1, 2]) ); // 3
경고( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
경고( getMaxSubSum([1, 2, 3]) ); // 6
경고( getMaxSubSum([-1, -2, -3]) ); // 0이 알고리즘에는 정확히 1개의 배열 패스가 필요하므로 시간 복잡도는 O(n)입니다.
여기에서 알고리즘에 대한 자세한 정보를 찾을 수 있습니다: 최대 하위 배열 문제. 그것이 왜 작동하는지 여전히 명확하지 않다면 위의 예에서 알고리즘을 추적하고 어떻게 작동하는지 확인하십시오. 그것은 어떤 단어보다 낫습니다.
샌드박스에서 테스트를 통해 솔루션을 엽니다.