題目描述
陣列是一個非常簡單的資料結構,可以用來儲存資料。舉例來說,陣列可以儲存一個班級裡所有學生的學號,也可以儲存世界上所有國家的名稱。
您可以寫出以下的程式來建立一個能儲存10個整數的陣列:
int[] myList = new int[10];
這個題目將會測試您對Java陣列的認知。
您將會得到一個擁有n個整數的陣列。若所有在子陣列中的整數相加之後是負數的,則稱這個子陣列為「Negative」。計算輸入的陣列擁有幾個「Negative」的子陣列。
子陣列由(主)陣列連續的元素組成。舉例來說,若陣列為{1,2,3,4,5},則{1}、{1,2,3}、{2,3,5}、{1,2,3,5}都算是這個陣列的子陣列。{1,2,5}不是子陣列,因為它在陣列{1,2,3,4,5}中並沒有連續。
原題網址
https://www.hackerrank.com/challenges/java-1d-array-easy
輸入格式
第一行包含一個整數n,最大值為100。接下來的一行有n個使用空格隔開的整數,範圍在-10000到10000之間(包含-10000和10000)。
輸出格式
輸出陣列中有多少個「Negative」的子陣列。
範例輸入
5
1 -2 4 -5 1
範例輸出
9
額外解釋
以下是「Negative」的子陣列索引範圍:
[0:1]
[0:3]
[0:4]
[1:1]
[1:3]
[1:4]
[2:3]
[3:3]
[3:4]
索引值從0開始。
解題概念
先實作出一個用來計算陣列指定索引範圍內元素加總的sum方法,接著再撰寫巢狀迴圈來產生所有子陣列的索引範圍。
參考答案
import java.util.Scanner;
public class Solution {
public static void main(final String[] args) {
final Scanner sc = new Scanner(System.in);
final int n = sc.nextInt();
final int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = sc.nextInt();
}
int counter = 0;
for (int length = 1; length <= n; ++length) {
final int end = n - length;
for (int start = 0; start <= end; ++start) {
if (sum(a, start, length) < 0) {
++counter;
}
}
}
System.out.println(counter);
}
private static int sum(final int[] a, final int start, final int length) {
int sum = 0;
for (int i = 0; i < length; ++i) {
sum += a[start + i];
}
return sum;
}
}